333
правки
Изменения
Нет описания правки
Будем передавать в качестве параметров рекурсий следующие переменные:
* <tex>vernode</tex> {{---}} номер(в массиве с деревом отрезков) текущей вершины дерева.
* <tex>l</tex>, <tex>r</tex> {{---}} левая и правая границы отрезков, за которые "отвечает" наша вершина.
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого отрезка.
<code>
int get_sum (int vernode, int l, int r, int a, int b)
{
if ([l,r] <tex>\bigcap</tex> [a, b] = <tex> \varnothing</tex>)
return 0;
if ([l,r] = [a, b])
return tree[vernode];
int m = (l + r) / 2;
return get_sum (ver node * 2, l, m, a, min(b, m)) + get_sum (ver node * 2 + 1, m + 1, r, max(a, m + 1), b);
}
</code>
