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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Переименуем функцию 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)));
}

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Дерево_Фенвика_с_модификацией_на_отрезке&oldid=1428