Дерево Фенвика для максимума

Про дерево Фенвика многие знают. Многие его используют. Однако считается, что деревом Фенвика нельзя находить максимум/минимум.
Мол, эта операция не ассоциативна. Однако небольшие изменения алгоритма позволяют нам решить и эту задачу тоже.
NB: Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.Тем, кто не знает, что такое дерево Фенвика, рекомендуется прочитать об этом где-нибудь, хоть в Кормене, хоть в статье на хабре

1.Постановка задачи

Есть массив. К нему выполняется много много запросов как на нахождение максимума на интервале, так и на увеличение значения в одной из ячеек.
Да, именно на увеличение. Значение в ячейке уменьшать нельзя, иначе алгоритм не работает.

2.Собственно алгоритм

Создадим класс — FenvikTree, который будет иметь два метода — Update(int i,double cost) и Max(int left,int right) — соответственно апдейт значения в i-ой ячейке и поиск максимума на интервале.
Как всегда в дереве Фенвика, нам понадобится k-минимальное число, такое что pow(2,k)>=a.size()
Хранить дерево будем в массиве.

Главное отличие от обычного дерева Фенвика

Нам понадобятся два массива, а не один, как в обычном дереве Фенвика, назовем их left и right
В i-й ячейке массива left будем хранить максимум на отрезке [i-G(i)+1,i], в i-й ячейке массива right— максимум на отрезке [i,i+G(i)-1] при i<pow(2,k) и на отрезке [i,i] при i=pow(2,k).
Собственно класс:

class FenvikTree
{
private:
    vector<double> a;
    vector<double> left;
    vector<double> right;
public:
    void PreProc();
    double Max(int left,int right);
    void Update(int i,double cost);
};

Функция PreProc() нужна, чтобы добавить в дерево наши первоначальные данные и выглядит ужасающе сложно:

void FenvikTree::PreProc(){
 for(int i=0;i<a.size();i++) Update(i+1,a[i]);
}

Обращаю внимание, именно i+1, т.к. наша функция перехода в массивах G(x) = x-(x&(x-1)) работает для x>0
Теперь напишем функцию Update:

void FenvikTree::Update(int r,double cost)
{
    a[r-1]=cost;
    int i=r;
    while(i<=pow(2.0,double(k)))
    {
        left[i]=max(left[i],cost);
        i=i+G(i);
    }
    i=r;
    while(i>0)
    {
        right[i]=max(right[i],cost);
        i=i-G(i);
    }
}

и Max:

double FenvikTree::Max(int l,int r){
    double res=0;
    int i=l;
    while(i+G(i)<=r)
    {
        res=max(res,right[i]);
        i=i+G(i);
    }
    if(a[i-1]>res) ans=i;
    res=max(res,a[i-1]);
    i=r;
    while(i-G(i)>=l)
    {
        res=max(res,left[i]);
        i=i-G(i);
    }
    return res;
}

Вот и все.

Как видите, дерево Фенвика для максимума можно написать очень просто и очень быстро(что иногда критично).

Автор: demist

Источник