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

3D дерево Фенвика

Многомерное бинарное индексированное дерево для трёхмерных префиксных запросов

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

def get(x, y, z):
    i = x
    ans = 0
    while i > 0:
        j = y
        while j > 0:
            k = z
            while k > 0:
                ans += F[i][j][k]
                k -= k & -k
            j -= j & -j
        i -= i & -i
    return ans

def add(x, y, z, d):
    i = x
    while i <= n:
        j = y
        while j <= n:
            k = z
            while k <= n:
                F[i][j][k] += d
                k += k & -k
            j += j & -j
        i += i & -i

s = list(map(int, input().split()))
while s[0] != 3:
    if s[0] == 1:
        _, x, y, z, d = s
        x += 1
        y += 1
        z += 1
        add(x, y, z, d)
    else:
        _, x1, y1, z1, x2, y2, z2 = s
        x1 += 1
        y1 += 1
        z1 += 1
        x2 += 1
        y2 += 1
        z2 += 1
        ans = get(x2, y2, z2)
        ans -= get(x1 - 1, y2, z2)
        ans -= get(x2, y1 - 1, z2)
        ans -= get(x2, y2, z1 - 1)
        ans += get(x1 - 1, y1 - 1, z2)
        ans += get(x1 - 1, y2, z1 - 1)
        ans += get(x2, y1 - 1, z1 - 1)
        ans -= get(x1 - 1, y1 - 1, z1 - 1)
        print(ans)
    s = list(map(int, input().split()))
⚙️ C++ (реализация)
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<vector<long long>>> F;

long long get(int x, int y, int z) {
    long long ans = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            for (int k = z; k > 0; k -= k & -k) {
                ans += F[i][j][k];
            }
        }
    }
    return ans;
}

void add(int x, int y, int z, int d) {
    for (int i = x; i <= n; i += i & -i) {
        for (int j = y; j <= n; j += j & -j) {
            for (int k = z; k <= n; k += k & -k) {
                F[i][j][k] += d;
            }
        }
    }
}

int main() {
    cin >> n;
    F.assign(n + 2, vector<vector<long long>>(n + 2, vector<long long>(n + 2, 0)));
    
    int t;
    while (cin >> t && t != 3) {
        if (t == 1) {
            int x, y, z, d;
            cin >> x >> y >> z >> d;
            x++; y++; z++;
            add(x, y, z, d);
        } else {
            int x1, y1, z1, x2, y2, z2;
            cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
            x1++; y1++; z1++; x2++; y2++; z2++;
            long long ans = get(x2, y2, z2);
            ans -= get(x1 - 1, y2, z2);
            ans -= get(x2, y1 - 1, z2);
            ans -= get(x2, y2, z1 - 1);
            ans += get(x1 - 1, y1 - 1, z2);
            ans += get(x1 - 1, y2, z1 - 1);
            ans += get(x2, y1 - 1, z1 - 1);
            ans -= get(x1 - 1, y1 - 1, z1 - 1);
            cout << ans << "\n";
        }
    }
    
    return 0;
}

Как работает 3D дерево Фенвика?

3D дерево Фенвика (3D Binary Indexed Tree) — это многомерное обобщение обычного дерева Фенвика для работы с трёхмерными массивами. Позволяет выполнять:

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

В трёхмерном случае каждый индекс хранит сумму по некоторому трёхмерному диапазону. Обновление и запрос требуют трёх вложенных циклов по младшим битам.

Для 3D: add и get используют три вложенных цикла
Внешний по x, средний по y, внутренний по z.

Формула суммы в параллелепипеде

sum(x1..x2, y1..y2, z1..z2) =
  get(x2,y2,z2)
  - get(x1-1,y2,z2) - get(x2,y1-1,z2) - get(x2,y2,z1-1)
  + get(x1-1,y1-1,z2) + get(x1-1,y2,z1-1) + get(x2,y1-1,z1-1)
  - get(x1-1,y1-1,z1-1)

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

Пространственная сложность: O(n³) — трёхмерный массив размером (n+1)×(n+1)×(n+1).

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

Ввод:

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

5
1 0 0 0 5
1 1 1 1 3
2 0 0 0 2 2 2
3

Вывод: 8

Сначала добавили 5 в (0,0,0), затем 3 в (1,1,1). Сумма в кубе (0,0,0)-(2,2,2) = 5+3 = 8.

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

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

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