← Назад к структурам данных

Дерево Фенвика (массовое обновление)

Прибавление на отрезке и точечный запрос за O(log n)

🐍 Python (реализация)
n, m = map(int, input().split())
F = [[0] * 2 for _ in range(n + 1)]

def get1(r, f):
    z = 0
    while r > 0:
        z += F[r][f]
        r -= r & -r
    return z

def get(r):
    return get1(r, 0) * r - get1(r, 1)

def add1(i, x, f):
    while i <= n:
        F[i][f] += x
        i += i & -i

def add(l, r, x):
    add1(l, x, 0)
    add1(r + 1, -x, 0)
    add1(l, x * (l - 1), 1)
    add1(r + 1, -x * r, 1)

for _ in range(m):
    s = list(input().split())
    if s[0] == "+":
        l, r, x = int(s[1]), int(s[2]), int(s[3])
        add(l, r, x)
    else:
        print(get(int(s[1])) - get(int(s[1]) - 1))
⚙️ C++ (реализация)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<vector<ll>> F;

ll get1(int r, int f) {
    ll z = 0;
    while (r > 0) {
        z += F[r][f];
        r -= r & -r;
    }
    return z;
}

ll get(int r) {
    return get1(r, 0) * r - get1(r, 1);
}

void add1(int i, ll x, int f) {
    while (i <= n) {
        F[i][f] += x;
        i += i & -i;
    }
}

void add(int l, int r, ll x) {
    add1(l, x, 0);
    add1(r + 1, -x, 0);
    add1(l, x * (l - 1), 1);
    add1(r + 1, -x * r, 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int m;
    cin >> n >> m;
    
    F.assign(n + 1, vector<ll>(2, 0));
    
    for (int i = 0; i < m; i++) {
        char type;
        cin >> type;
        if (type == '+') {
            int l, r, x;
            cin >> l >> r >> x;
            add(l, r, x);
        } else {
            int p;
            cin >> p;
            cout << get(p) - get(p - 1) << "\n";
        }
    }
    
    return 0;
}

Как работает дерево Фенвика для массовых обновлений?

Модифицированное дерево Фенвика позволяет выполнять прибавление на отрезке [l, r] и точечный запрос значения элемента за O(log n). Для этого используется техника двух массивов — диапазонных и точечных запросов.

Основная идея

Вместо хранения самих значений, мы храним два дерева Фенвика, которые позволяют восстановить значение элемента через сумму вкладов от всех обновлений.

Формула для значения в точке p:
value(p) = get1(p, 0) * p - get1(p, 1)

Прибавление на отрезке [l, r] на x

Точечный запрос

Значение элемента p = get(p) - get(p-1), где get(r) — сумма префикса.

Сложность операций: O(log n) — каждая операция выполняется за время, пропорциональное количеству битов.

Пространственная сложность: O(n) — два дерева размера n+1.

Формат ввода и вывода

Ввод:

Вывод:

Пример ввода:

10 6
+ 1 5 3
? 3
+ 3 7 2
? 3
? 5
+ 1 10 1
? 5

Вывод:

3
5
5
2

Пояснение:
Изначально все нули.
После + 1 5 3: A[3] = 3 → вывод 3
После + 3 7 2: A[3] = 3+2=5, A[5] = 3+2=5 → вывод 5, 5
После + 1 10 1: A[5] = 5+1=6 → вывод 6

Попробовать массовое дерево Фенвика онлайн

Введите запросы:

Результат появится здесь...