Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Минимум на неизменяемом отрезке О(NlogN + KlogN)

Дан массив из N целых чисел и K запросов, состоящих из двух индексов.
Необходимо для каждого запроса вывести минимальный из элементов, расположенных между индексами в запросе.

    Будем использовать дерево отрезков. Тогда все запросы и события будут выполняться за O(logN).

Асимптотика O(NlogN + KlogN).


Листинг C++

class tree
{
public :
    int a;
    int Min;
    int l, r;
    tree * left, * right;
    
    tree (int _l, int _r)
    {
        l = _l;
        r = _r;
        a = 1e9;
        Min = 1e9;
        
        if (l == r) return ;        
        int m = (l + r) / 2;        
        left = new tree (l, m);
        right = new tree (m + 1, r);
    }
    
    void modify (int i, int x)    // изменение i-того элемента
    {
        if (l == r && l == i)
        {
            a = x;
            Min = x;
            return ;
        }
        
        int m = (l + r) / 2;
        if (l <= i && i <= m)
            left->modify (i, x);
        else
            right->modify (i, x);
        
        Min = min (left->Min, right->Min);
    }
    
    int minimum (int _l, int _r)    // минимум элементов от i до j
    {
        _l = max (_l, l);
        _r = min (_r, r);
        
        if (_l == l && _r == r) return Min;
        
        int ans = 1e9;
        if (left->l <= _l && _l <= left->r)
            ans = left->minimum (_l, _r);
        if (right->l <= _r && _r <= right->r)
            ans = min (ans, right->minimum (_l, _r));
        
        return ans;
    }
};


14:26
05.08.2009