Introduction to Segment tree презентация

элементу значение d
2) Получить сумму на отрезке [l;r]
The Example of queries for the segment tree:
To add a value d to the value of i-th element
To get sum on the segment [l;r]

*= 2;
t.resize(2 * size, 0); //0 – neutral element for “+”
for (int i = 0; i < (int)a.size(); i++)
t[i + size] = a[i];
for (int i = size - 1; i > 0; i--)
t[i] = t[2*i]+t[2*i+1];
}

int d){
if (tl == tr){
t[v] += d;
return;
}
int mid = (tl + tr) / 2;
if (i <= mid) change(2*v, tl, mid, i, d);
else change(2*v+1, mid + 1, tr, i, d);
t[v] = t[2*v] + t[2*v+1];
}

change(1, 0, size - 1, i, d); //Start

r){
if (l > r) return 0;
if (tl == l && tr == r){
return t[v];
}
int mid = (tl + tr) / 2;
int left_sum = sum(2*v, tl, mid, l, min(r, mid));
int right_sum = sum(2*v+1, mid+1, tr, max(l, mid+1), r);
return left_sum + right_sum;
}

sum(1, 0, size - 1, l, r);

d
2) Получить сумму на [l;r]
Для этого нам придётся воспользоваться методом «запаздывающего обновления».
Requests:
1) Add the value d to every element on the segment [l;r]
2) Get sum on the segment [l;r]
We use the method of “lazy propagation”

“lazy propagation”
int size;

void init(vector &a, int n){
size = 1;
while(size <= n) size *= 2;
t.resize(2 * size, 0);
add.resize(2 * size, 0);
for (int i = 0; i < (int)a.size(); i++)
t[i + size] = a[i];
for (int i = size - 1; i > 0; i--)
t[i] = t[2*i]+t[2*i+1];
}

};

0;
}

int r, int d){
if (l > r) return;
if (tl == l && tr == r){
add[v] += d;
return;
}
push(v);
int mid = (tl + tr) / 2;
change(2*v, tl, mid, l, min(r, mid), d);
change(2*v+1, mid + 1, tr, max(l, mid + 1), r, d);
t[v] = t[2*v] + (mid - tl + 1) * add[2*v] + t[2*v+1] + (r - mid) * add[2*v+1];
}

change(1, 0, size - 1, l, r, d);

r){
if (l > r) return 0;
if (tl == l && tr == r){
return t[v] + add[v] * (r - l + 1);;
}
push(v);
int mid = (tl + tr) / 2;
int left_sum = sum(2*v, tl, mid, l, min(r, mid));
int right_sum = sum(2*v+1, mid+1, tr, max(l, mid+1), r);
t[v] = t[2*v] + (mid - tl + 1) * add[2*v] + t[2*v+1] + (r - mid) * add[2*v+1];
return left_sum + right_sum;
}

sum(1, 0, size - 1, l, r);

массового обновления
E-maxx. Дерево отрезков – описано большое количество задач, которые решаются деревом отрезков с решением.
Codeforces (Eng article)