software engineer
19,2
рейтинг
24 ноября 2012 в 22:05

Разработка → Дерево Фенвика для максимума

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

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

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

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

Создадим класс — FenwickTree, который будет иметь два метода — 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 FenwickTree
{
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 FenwickTree::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 FenwickTree::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 FenwickTree::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;
}


Вот и все.

Как видите, дерево Фенвика для максимума можно написать очень просто и очень быстро(что иногда критично).
Nikita Starichkov @demist
карма
20,2
рейтинг 19,2
software engineer
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (9)

  • +4
    «Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.»

    Вряд ли это надо рассказывать тем, кто знает, что такое дерево Фенвика, т.к. дерево Фенвика для максимума тривиально.
    • 0
      писал это потому что в статье на хабре, на которую идет ссылка в начале ничего не говорит про максимум, а в комментариях к ней некоторые люди утверждают, что для максимума написать невозможно. и в некоторых других источниках видел, что отрицается возможность для максимума
      • 0
        скорее, можно рассматривать этот пост как дополнение к основному посту про дерево Фенвика
    • 0
      Я бы сказал, что оно тривиально для максимума на префиксе/суффиксе, а не на отрезке. Реализации для отрезка я никогда не встречал и ни от кого не слышал.
      • +1
        вот именно, что префикс/суффикс тривиален.
        когда я говорил кому-то про дерево фенвика для максимума, все именно это и говрят — префикс-суффикс.
        а вот на отрезке это нечто, мало кому знакомое
  • +1
    Несколько мыслей по этому поводу:

    • Зачем нам нужен старший бит в числе? Можно же просто делать цикл до размера массива/нуля. Обычный Фенвик прекрасно работает на массивах произвольного размера
    • Дерево Фенвика по-английски пишется как Fenwick tree
    • Разве нельзя сделать инициализацию за линию? Дополнило бы
    • Статья была бы лучше, если бы провелось хоть какое-то сравнение с, например, деревом отрезков и sparse table по времени — инициализация, изменение, запрос
    • И мне непонятно, чем такая реализация лучше дерева отрезков, которое занимает меньше места (обновление — один for, две строки; запрос — один while, два if, шесть строчек) и интуитивнее понятнее.
    • 0
      Правописание исправил, спасибо указание.
      Про сравнение со ST и дерево отрезков — это есть в статье, на которую я ссылаюсь.
      Про реализацию. Хм, Вы первый человек от которого я слышу, что дерево отрезков проще.Мнение большинства, вроде бы, ровно наоборот.=) Да, оно может быть, чуть-чуть понятнее, но и фенвик не сложный.
      Инициализация за линию? что-то мне не приходит пока в голову, как
      Про старший бит — мы же идем с двух концов, и нам надо точно знать как они пересекутся
      • 0
        Интересна именно данная реализация — она существенно отличается, например, наличием нескольких массивов и, соответственно, большими прыжками по памяти.

        Нет, имеется введу, что моё дерево отрезков проще Вашего кода, а мой Фенвик для суммы, в свою очередь, проще дерева отрезков (одному for'у из одной команды на каждую операцию).

        Не вникал, но хочется сказать, что «детьми вершины» являются только те, которые располагаются левее/правее (в зависимости от массива). Просто надо перебрать вершины в нужном порядке и релаксировать только из текущей вершины. Можете думать об этом, как о динамике.

        Понял. Верно ли, что получается что-то в стиле sparse? Еще совет по улучшению: выложить хоть что-то, кроме кода. Например, фразу «в одном массиве будет то-то, в другом — то-то, когда приходит запрос, мы разбиваем его на два почти всегда пересекающихся размером 2^k»
        • 0
          Что может быть проще пары while'ов? Если же сравнивать длину кода, то я за этим не гнался.Задача была написать понятный код, который говорит сам за себя. Поэтому кроме кода мало чего есть. Думается мне, что человек, знакомый с деревом Фенвика, легко поймет и эту его модификацию.

          Про инициализацию — все равно пока не думаю, что так возможно.
          Нет, на sparse это не сильно похоже.Ну только с очень-очень большой долей абстракции.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.