Привет, хабр!

Это моя вторая статья из серии «то что я не нашел в интернетах». Кому интересно — добро пожаловать под кат.


Начнем с постановки задачи:

• Дан массив из N элементов, где 1 ? N ? 100 000,
• и K запросов (1 <= K <= 100 000) вида:
  
  1. Присвоить элементам с L по R значение V (0 ? V ? 100 000 000)
  2. Найти сумму элементов отрезка [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.