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

Конспекта пока нет, можете почитать алгокод.

ДО на сумму и прибавление на отрезке

Ниже - пример хорошей (на взгляд автора) реализации ДО с использованием структуры для вершин дерева.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct node {
    int sum, lazy;

    explicit node(int sum = 0, int lazy = 0) : sum(sum), lazy(lazy) {};
};

vector<node> tree;

void push(int v, int le, int ri) {
    if (le + 1 < ri) {
        tree[2 * v + 1].lazy += tree[v].lazy;
        tree[2 * v + 2].lazy += tree[v].lazy;
    }
    tree[v].sum += tree[v].lazy * (ri - le);
    tree[v].lazy = 0;
}

node merge(node a, node b) {
    return node(a.sum + b.sum);
}

void add(int v, int le, int ri, int l, int r, int x) {
    if (r <= le || ri <= l) {
        return;
    }
    if (l <= le && ri <= r) {
        tree[v].lazy += x;
        return;
    }
    int m = (le + ri) / 2;

    push(v, le, ri);

    add(2 * v + 1, le, m, l, r, x);
    add(2 * v + 2, m, ri, l, r, x);

    push(2 * v + 1, le, m);
    push(2 * v + 2, m, ri);

    tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
}

node get(int v, int le, int ri, int l, int r) {
    push(v, le, ri);
    if (r <= le || ri <= l) {
        return node();
    }
    if (l <= le && ri <= r) {
        return tree[v];
    }
    int m = (le + ri) / 2;

    push(2 * v + 1, le, m);
    push(2 * v + 2, m, ri);
    return merge(get(2 * v + 1, le, m, l, r), get(2 * v + 2, m, ri, l, r));
}

int main() {
    int n;
    cin >> n;
    tree.resize(4 * n);

    int m;
    cin >> m;
    while (m--) {
        int type;
        cin >> type;
        if (type == 2) {
            int l, r;
            cin >> l >> r;
            cout << get(0, 0, n, l, r).sum << '\n';
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            add(0, 0, n, l, r, x);
        }
    }
    return 0;
}