Дерево Фенвика с модификацией на отрезке

Переименуем функцию sum() в функцию alpha(), а функцию add() — в функцию modifyAlphas().

int alpha(int r) {
    int res = 0;
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        res += b[i];
    return res;
}

void modifyAlphas(int pos, int val) {
    for (int i = pos; i < MAX_SIZE; i |= i + 1)
        b[i] += val;
}

Тогда в общем случае мы можем считать, что вызов alpha(i) возвращает результат некоторой функции α(i) (или элемент некоторого массива α[i]), а вызов modifyAlphas(pos, val) добавляет значение val ко всем α(i) (или α[i]), у которых i >= pos. В зависимости от того, как трактовать значение α(i), можно получить несколько применений дерева Фенвика. Если считать, что α(i) — сумма элементов массива a[] от a[0] до a[i], то мы получим базовую версию дерева Фенвика, в которой функция modifyAlphas() изменяет элемент массива a[].

Запрос отдельных элементов и модификация на отрезке

Пусть α(i) — значение i-го элемента массива a[]. Тогда вызов modifyAlphas(pos, val) добавит val ко всем элементам a[], у которых i >= pos. Следовательно, чтобы увеличить только элементы с индексами от l до r, нужно вызвать modifyAlphas(l, val) и modifyAlphas(r + 1, -val).

int get(int pos) {
    return alpha(pos);
}

int add(int l, int r, int val) {
    modifyAlphas(l, val);
    modifyAlphas(r + 1, -val);
}

Запрос на отрезке и модификация на отрезке

Пусть используется второе дерево Фенвика, реализующее функции beta() и modifyBetas(), и пусть (β(i) * i + α(i)) — сумма элементов массива a[] от a[0] до a[i]. Далее, пусть элементы массива a[] с индексами от l до r увеличились на величину val. Рассмотрим, как при этом изменится сумма элементов массива a[] от a[0] до a[i]:

• Если i < l, то сумма не изменилась, и значение (β(i) * i + α(i)) ей соответствует.
• Если l <= i <= r, то сумма увеличилась на (val * (i - l + 1)). Следовательно, к β(i) нужно добавить val, а к α(i) — (val * (-l + 1)).
• Если i > r, то сумма увеличилась на (val * (r - l + 1)). Следовательно, β(i) изменять не нужно, а к α(i) нужно добавить (val * (r - l + 1)).

int sum(int r) {
    return beta(r) * r + alpha(r);
}

void add(int l, int r, int val) {
    modifyBetas(l, val);
    modifyAlphas(l, val * (-l + 1));
    modifyBetas(r + 1, -val);     //modifyBetas(r + 1, 0 - val);
    modifyAlphas(r + 1, val * r); //modifyAlphas(r + 1, (val * (r - l + 1)) - (val * (-l + 1)));
}

Ссылки

• petr-mitrichev.blogspot.ru — Fenwick tree range updates
• topcoder.com — How to modify BIT to update the ranges and query the ranges?
• topcoder.com — Range update in BIT
• kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree