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

    Про дерево Фенвика многие знают. Многие его используют. Однако считается, что деревом Фенвика нельзя находить максимум/минимум.
    Мол, эта операция не имеет обратной. Однако небольшие изменения алгоритма позволяют нам решить и эту задачу тоже.
    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;
    }
    


    Вот и все.

    Как видите, дерево Фенвика для максимума можно написать очень просто и очень быстро(что иногда критично).
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

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

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

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

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

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

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