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

Дерево отрезков

Сумма на отрезке и точечное обновление за O(log n)

🐍 Python
n, m = map(int, input().split())
A = list(map(int, input().split()))
tree = [0] * (n * 4)

def build(v, l, r):
    if l == r:
        tree[v] = A[l]
        return
    m = (l + r) // 2
    build(v * 2, l, m)
    build(v * 2 + 1, m + 1, r)
    tree[v] = tree[v * 2] + tree[v * 2 + 1]

def update(v, l, r, z, p):
    if l == r:
        tree[v] = z
        return
    m = (l + r) // 2
    if p <= m:
        update(v * 2, l, m, z, p)
    else:
        update(v * 2 + 1, m + 1, r, z, p)
    tree[v] = tree[v * 2] + tree[v * 2 + 1]

def get(v, l, r, l0, r0):
    if l == l0 and r == r0:
        return tree[v]
    m = (l + r) // 2
    s1 = s2 = 0
    if l0 <= m:
        s1 = get(v * 2, l, m, l0, min(r0, m))
    if r0 >= m + 1:
        s2 = get(v * 2 + 1, m + 1, r, max(l0, m + 1), r0)
    return s1 + s2

build(1, 0, n - 1)

for _ in range(m):
    f, l, r = map(int, input().split())
    if f == 1:
        print(get(1, 0, n - 1, l - 1, r - 1))
    else:
        update(1, 0, n - 1, r, l - 1)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;
using T = long long;

vector<T> tree, A;

void build(T v, T l, T r) {
    if (l == r) {
        tree[v] = A[l];
        return;
    }
    T m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

void update(T v, T l, T r, T z, T p) {
    if (l == r) {
        tree[v] = z;
        return;
    }
    T m = (l + r) / 2;
    if (p <= m)
        update(v * 2, l, m, z, p);
    else
        update(v * 2 + 1, m + 1, r, z, p);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

T get(T v, T l, T r, T l0, T r0) {
    if (l == l0 && r == r0)
        return tree[v];
    T m = (l + r) / 2;
    T s1 = 0, s2 = 0;
    if (l0 <= m)
        s1 = get(v * 2, l, m, l0, min(r0, m));
    if (r0 >= m + 1)
        s2 = get(v * 2 + 1, m + 1, r, max(l0, m + 1), r0);
    return s1 + s2;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    T n, m;
    cin >> n;
    A.resize(n);
    tree.resize(n * 4 + 1);
    
    for (T i = 0; i < n; i++)
        cin >> A[i];
    
    build(1, 0, n - 1);
    
    cin >> m;
    for (T i = 0; i < m; i++) {
        T f, l, r;
        cin >> f >> l >> r;
        if (f == 1) {
            cout << get(1, 0, n - 1, l - 1, r - 1) << "\n";
        } else {
            update(1, 0, n - 1, r, l - 1);
        }
    }
    
    return 0;
}

Как работает дерево отрезков?

Дерево отрезков — это структура данных, которая позволяет выполнять запросы на отрезке (сумма, минимум, максимум) и точечные обновления за O(log n).

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

Массив разбивается на отрезки, каждый узел дерева хранит информацию о своём отрезке (например, сумму). Корень хранит информацию обо всём массиве, листья — об отдельных элементах.

                    [0..7]
                   /      \
              [0..3]      [4..7]
              /    \      /    \
          [0..1] [2..3] [4..5] [6..7]
           / \    / \    / \    / \
         [0][1] [2][3] [4][5] [6][7]

Основные операции

Параметры функций

Временная сложность: O(log n) на запрос и обновление.

Пространственная сложность: O(4n) ≈ 4n памяти.

Пример работы

Рассмотрим массив: A = [1, 3, 5, 7, 9, 11] (n=6)

Дерево отрезков (суммы):

                    [0..5] = 36
                   /          \
          [0..2] = 9          [3..5] = 27
           /     \             /     \
     [0..1]=4   [2]=5     [3..4]=16   [5]=11
      /    \               /    \
    [0]=1  [1]=3         [3]=7  [4]=9

Операции:
1. get(1, 3) → сумма A[1..3] = 3+5+7 = 15
2. update(2, 10) → A[2] = 10
   Обновляем лист [2]=10, затем [0..2]=1+3+10=14, корень=14+27=41
3. get(0, 5) → сумма всех элементов = 41

Результат: быстрый ответ на запросы суммы и обновления

Попробовать дерево отрезков онлайн

Введите массив и запросы (1 l r — сумма, 2 p z — обновление):

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