Дисклеймер

Я нашел в интернете всего одну статью про встречное дерево Фенвика, которое должно расширять возможности обычного дерева Фенвика, и не смог ее понять. Однако недавно мне пришла в голову идея, как использовать этот трюк с двоичными подъемами, чтобы модифицировать дерево Фенвика и использовать его, например, для нахождения минимума на отрезке. Кроме того, я расскажу про еще одно дерево, достаточно схожее с деревом Фенвика.

В чем вообще проблема и тот самый трюк

Стандартное дерево Фенвика работает только на обратимых операциях (сумма, xor), так как мы быстро(за $$$\mathcal{O}(\log_2{n})$$$) можем получать значения только на префиксах. Оказывается, что за почти эту же асимптотику мы можем получать значения на любых отрезках.

Чтобы лучше понимать, что будет дальше происходить рекомендую прочитать эту статью. Если вкратце, там написано, что для каждой вершины нужно хранить максимальный прыжок. Задаются эти прыжки следующим образом: если длина прыжка из предыдущей вершины равна длине прыжка из той вершины, в которую мы прыгаем из предыдущей, то наш текущий максимальный прыжок будет покрывать эти два, иначе текущий прыжок просто ведет в предыдущую вершину. Если внимательно посмотреть на длины прыжков, то видно, что это числа, которые равны $$$2^n - 1$$$. Теперь чтобы прыгнуть одной вершины в другую, нужно прыгать по максимальному прыжку, когда это возможно, иначе просто на одну вершину вверх. Интуитивно понятно, что количество прыжков $$$\mathcal{O}(\log_2{n})$$$, однако строгое доказательство достаточно сложное и большое.

Связь с деревом Фенвика

Заметим, что в дереве Фенвика мы делаем почти тоже самое! И правда, мы буквально прыгаем по отрезкам размера $$$2^n$$$.

Разберем детальнее алгоритм ответа на запрос. Допустим, правая граница запроса равна $$$r$$$. Если отрезок, за который отвечает элемент с индексом $$$r$$$, входит в наш запрос, обрабатываем его и делаем прыжок по отрезку. Иначе обрабатываем один элемент и уменьшаем $$$r$$$ на один. К сожалению, так мы разобьем запрос не на $$$\mathcal{O}(\log_2{n})$$$ отрезков, как нам могло показаться. Например, если мы возьмем правую границу $$$r = 2^n - 1$$$, а левую $$$l = 2^{n - 1} + 1$$$, то нам придется обработать $$$\mathcal{O}(\log_2^2{n})$$$ отрезков. Однако на практике это работает быстро (возможно в тесты просто не добавляют подобные контрпримеры). Реализация

У этого подхода есть и другие минусы. Во-первых, его достаточно сложно обобщать на бОльшие размерности. Для правильных переходов на 1 необходимо поддерживать деревья Фенвика меньших размерностей. Например, для такой структуры в 2D надо поддерживать отдельно два списка 1D деревьев Фенвика (по столбцам и строкам). Для 3D нужны 3 списка 2D деревьев и 3 матрицы 1D деревьев. Реализация получается громоздкой, с большой константой, лучше использовать дерево отрезков снизу. Во-вторых, сложности с обновлениями. Так как в дереве Фенвика у вершины может быть $$$\mathcal{O}(\log_2{n})$$$ детей, обновление каждого предка может занимать $$$\mathcal{O}(\log_2{n})$$$. В итоге, на каждую размерность добавляется лишний логарифм. Для 2D дерева асимптотика получается грустная $$$\mathcal{O}(q \log_2^6{n})$$$. В-третьих ответ на запрос более медленный, чем в стандартном дереве Фенвика.

Несите другое дерево

Давайте попробуем сделать свое дерево на основе идеи с прыжками. Получится что-то такое:

Самый правый элемент отрезка отвечает за значение на нем. Заметим, что теперь у каждой вершины всего два ребенка, да и вообще это дерево — лес обычных деревьев отрезков, но по особому упорядоченных. Построение дерева такое же, как и построение максимальных прыжков, отвечаем на запросы аналогично. Однако теперь мы можем легко обрабатывать обновления в точке.

const int inf = 1e9 + 10;

struct Node {
    int len = 1, par = -1, val;
};

vector<Node> tr;
vector<int> a;

void init() {
    int n = a.size();
    tr.resize(n);
    for (int i = 0; i < n; i++) {
        tr[i].val = a[i];
        if (i == 0) continue;
        int l1 = tr[i - 1].len;
        if (i - l1 == 0) continue;
        int l2 = tr[i - 1 - l1].len;
        if (l1 == l2) {
            tr[i].val = min({tr[i].val, tr[i - 1].val, tr[i - 1 - l1].val});
            tr[i - 1].par = i;
            tr[i - 1 - l1].par = i;
            tr[i].len = l1 + l2 + 1;
        }
    }
}

int gmin(int l, int r) { // [l, r)
    r--;
    int curmin = inf;
    while (r >= l) {
        if (r - tr[r].len + 1 >= l) {
            curmin = min(curmin, tr[r].val);
            r -= tr[r].len;
        } else {
            curmin = min(curmin, a[r]);
            r--;
        }
    }
    return curmin;
}

void setval(int idx, int val) {
    a[idx] = val;
    while (idx != -1) {
        if (tr[idx].len > 1) {
            tr[idx].val = min({a[idx], tr[idx - 1].val, tr[idx - (tr[idx].len - 1) / 2 - 1].val});
        } else {
            tr[idx].val = a[idx];
        }
        idx = tr[idx].par;
    }
}

К сожалению, с этим подходом мы тоже не можем избежать громоздкой реализации при бОльших размерностях. Кроме того, теперь есть дополнительные проблемы, если мы захотим сделать дерево неявным. Дело в том, что мы должны уметь очень быстро получать длину определенного отрезка. Единственный алгоритм, который мне пришел в голову, работает за $$$\mathcal{O}(\log_2{C})$$$, где $$$C$$$ — максимальная координата. На каждом шаге мы ищем максимальное такое $$$n$$$, что $$$2^n - 1$$$ меньше, чем индекс текущего элемента, и запускаем этот же алгоритм от $$$idx - (2^n - 1)$$$. Если $$$idx = 2^n - 1$$$, то это и есть искомая длина. Таким образом, при неявности к асимптотике добавляется логарифм.

В любом случае, я считаю, что такая идея запросов на отрезке заслуживает внимания. Надеюсь, статья вам понравилась.