Привет, хабр!
Это моя вторая статья из серии «то что я не нашел в интернетах». Кому интересно — добро пожаловать под кат.
Начнем с постановки задачи:
- Дан массив из N элементом, где 1 <= N <= 100 000,
- и K запросов (1 <= K <= 100 000) вида:
- присвоить элементам с L по R значение V (0 <= V <= 100 000 000)
- найти сумму элементов отрезка [L; R]
Значение суммы мы будем хранить в массиве value, а значение которое нужно присвоить элементам данного поддерева будем хранить в массиве delta. Первичное заполнение массивов ничем не отличается от стандартного дерева отрезков:
long[] value; long[] delta; long default_delta = -1; // должно быть невозможным значением void init(long[] a){ int nodes = a.length << 2; tree = new long[nodes]; delta = new long[nodes]; build(a, 1, 0, a.length-1); } void build(long[] a, int v,int tl,int tr){ if(tl == tr) tree[v] = a[tl]; else{ int mid = (tl+tr)>>1; build(a, 2*v, tl, mid); build(a, 2*v+1, mid+1, tr); tree[v] = tree[v*2]+tree[v*2+1]; delta[v] = default_delta; } } Теперь нужно научиться обновлять значение на отрезке. Для этого мы будем использовать «отложенные модификации», то есть будем помечать новым значеним только корни соответсвующих поддеревьев:
void update(int root, int left, int right, int from, int to, long delta) { if (left > to || right < from) return; if (left >= from && right <= to) { updateFull(root, left, right, from, to, delta); return; } int middle = (left + right) >> 1; updatePreProcess(root, left, right, from, to, delta, middle); update(2 * root + 1, left, middle, from, to, delta); update(2 * root + 2, middle + 1, right, from, to, delta); updatePostProcess(root, left, right, from, to, delta, middle); } void updateFull(int root, int left, int right, int from, int to, long delta) { value[root] = accumulate(value[root], delta, right - left + 1); delta[root] = joinDelta(delta[root], delta); } void updatePreProcess(int root, int left, int right, int from, int to, long delta, int middle) { pushDown(root, left, middle, right); } void updatePostProcess(int root, int left, int right, int from, int to, long delta, int middle) { value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]); } void pushDown(int root, int left, int middle, int right) { value[2 * root + 1] = accumulate(value[2 * root + 1], delta[root], middle - left + 1); value[2 * root + 2] = accumulate(value[2 * root + 2], delta[root], right - middle); delta[2 * root + 1] = joinDelta(delta[2 * root + 1], delta[root]); delta[2 * root + 2] = joinDelta(delta[2 * root + 2], delta[root]); delta[root] = default_delta; } long accumulate(long value, long delta, int length) { if(delta != default_delta) return delta * length; return value; } long joinDelta(long was, long delta) { if(delta != default_delta) // return delta; return was; } long joinValue(long left, long right) { return left + right; } Теперь остается только научиться пересчитывать сумму на отрезке, если это необходимо:
long query(int root, int left, int right, int from, int to) { if (left > to || right < from) return 0; if (left >= from && right <= to) return queryFull(root, left, right, from, to); int middle = (left + right) >> 1; queryPreProcess(root, left, right, from, to, middle); long leftResult = query(2 * root + 1, left, middle, from, to); long rightResult = query(2 * root + 2, middle + 1, right, from, to); return queryPostProcess(root, left, right, from, to, middle, leftResult, rightResult); } void queryPreProcess(int root, int left, int right, int from, int to, int middle) { pushDown(root, left, middle, right); } long queryPostProcess(int root, int left, int right, int from, int to, int middle, long leftResult, long rightResult) { return joinValue(leftResult, rightResult); } long queryFull(int root, int left, int right, int from, int to) { return value[root]; } На этом, вроде, все. Снова надеюсь, что кому-то пригодится.
p.s. Часть код взята и в некоторых местах переделанна из библиотеки Chelper’a.
ссылка на оригинал статьи http://habrahabr.ru/post/264087/
Добавить комментарий