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

Запрос на отрезке и модификация отдельных элементов

int t[4 * 100010];

void build(int v, int vl, int vr, int a[]) {
    if (vl == vr) {
        t[v] = a[vl];
        return;
    }
    int vm = vl + (vr - vl) / 2;
    build(2 * v + 1, vl, vm, a);
    build(2 * v + 2, vm + 1, vr, a);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
}

int query(int v, int vl, int vr, int l, int r) {
    if (l > r)
        return 0;
    if (vl == l && r == vr)
        return t[v];
    int vm = vl + (vr - vl) / 2;
    int ql = query(2 * v + 1, vl, vm, l, min(r, vm));
    int qr = query(2 * v + 2, vm + 1, vr, max(l, vm + 1), r);
    return ql + qr;
}

void modify(int v, int vl, int vr, int pos, int val) {
    if (vl == vr) {
        t[v] += val;
        return;
    }
    int vm = vl + (vr - vl) / 2;
    if (pos <= vm)
        modify(2 * v + 1, vl, vm, pos, val);
    else
        modify(2 * v + 2, vm + 1, vr, pos, val);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
}

Запрос на отрезке и модификация на отрезке

int t[4 * 100010], add[4 * 100010];

void push(int v, int vl, int vr) {
    if (vl != vr) {
        add[2 * v + 1] += add[v];
        add[2 * v + 2] += add[v];         
    }
    t[v] += add[v] * (vr - vl + 1);
    add[v] = 0;
}

void build(int v, int vl, int vr, int a[]) {
    if (vl == vr) {
        t[v] = a[vl];
        return;
    }
    int vm = vl + (vr - vl) / 2;
    build(2 * v + 1, vl, vm, a);
    build(2 * v + 2, vm + 1, vr, a);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
}

int query(int v, int vl, int vr, int l, int r) {
    if (l > r)
        return 0;
    push(v, vl, vr);
    if (vl == l && r == vr)
        return t[v];   //return t[v] + add[v] * (vr - vl + 1);
    int vm = vl + (vr - vl) / 2;
    int ql = query(2 * v + 1, vl, vm, l, min(r, vm));
    int qr = query(2 * v + 2, vm + 1, vr, max(l, vm + 1), r);
    return ql + qr;
}

void modify(int v, int vl, int vr, int l, int r, int val) {
    if (l > r)
        return;
    push(v, vl, vr);
    if (vl == l && r == vr) {
        add[v] += val;
        return;
    }
    int vm = vl + (vr - vl) / 2;
    modify(2 * v + 1, vl, vm, l, min(r, vm), val);
    modify(2 * v + 2, vm + 1, vr, max(l, vm + 1), r, val);
    //t[v] = (t[2 * v + 1] + add[2 * v + 1] * (vm - vl + 1)) + (t[2 * v + 2] + add[2 * v + 2] * (vr - vm));
    int ql = query(2 * v + 1, vl, vm, vl, vm);
    int qr = query(2 * v + 2, vm + 1, vr, vm + 1, vr);
    t[v] = ql + qr;
}

Ссылки

• e-maxx.ru — Дерево отрезков
• neerc.ifmo.ru/wiki — Дерево отрезков
• informatics.mccme.ru — Курс «Структуры данных» — часть 5
• VisuAlgo — Segment Tree
• CodeLibrary — Segment tree
• Algos — Segment Tree (Assign-Sum)