307. Запрос суммы диапазона, изменяемый (Range Sum Query - Mutable)

Задание.

Дан целочисленный массив nums, обработайте несколько запросов следующих типов:

Обновите значение элемента в nums. Вычислите сумму элементов nums между индексами left и right включительно, где left <= right. Реализуйте класс NumArray:

• NumArray(int[] nums) инициализирует объект целочисленным массивом nums.

• void update(int index, int val) Обновляет значение nums[index], чтобы оно было действительным.

• int sumRange(int left, int справа) Возвращает сумму элементов nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right])..

Пример 1.

Входные данные:

"NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Результат: [null, 9, null, 8]

Объяснение:

NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Решение.

class NumArray {
private:
    vector<int> t;
    int n;
    void inc (int i, int delta) {
        for (; i < n; i = (i | (i+1)))
            t[i] += delta;
    }
    int sum (int r) {
        int res = 0;
        for (r = min(r,n-1); r >= 0; r = (r & (r+1)) - 1)
            res += t[r];
        return res;
    }
public:
    NumArray(vector<int>& nums) {
        n = nums.size();
        t.assign (n, 0);
        for (int i = 0; i < n; i++) {
            inc (i, nums[i]);
        }
    }

    void update(int index, int val) {
        inc(index, val - sumRange(index, index));
    }

    int sumRange(int left, int right) {
        return sum (right) - sum (left-1);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */

Способ решения.

Для решения подобных задач используется Binary Indexed Tree (двоично-индексированное дерево) или дерево Фенвика.

Дерево Фенвика – это структура данных, дерево на массиве, обладающее следующими свойствами:

1) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время O (log N)

2) позволяет изменять значение любого элемента за O (log N)

3) требует O (N) памяти, а точнее, ровно столько же, сколько и массив из N элементов;

4) легко обобщается на случай многомерных массивов.

Наиболее распространённое применение дерева Фенвика – для вычисления суммы на отрезке, т.е. функция G (X1, ..., Xk) = X1 + ... + Xk.

Дерево Фенвика было впервые описано в статье “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).

Описание.

Предположим (для определенности), что дерево используется для получения сумм.

Пусть дан массив A[0..N-1]. Дерево Фенвика - массив T[0..N-1], в каждом элементе которого хранится сумма некоторых элементов массива A: T_i = сумма A_j для всех F(i) <= j <= i,

где F(i) – некоторая функция (определим позднее)

Псевдокод для суммы

int sum (int r)
{
    int result = 0;
    while (r >= 0) {
        result += t[r];
        r = f(r) - 1;
    }
    return result;
}

Псевдокод для изменения

void inc (int i, int delta)
{
    для всех j, для которых F(j) <= i <= j
    {
        t[j] += delta;
    }
}

Подробнее о дереве Фенвика:

• http://e-maxx.ru/algo/fenwick_tree

• https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

• https://habr.com/ru/post/112828/

Другие задачи

303. Запрос суммы диапазона, неизменяемый (Range Sum Query - Immutable)

304. Запрос суммы 2D-диапазона (Range Sum Query 2D - Immutable)