Propogation 없는 lazy 세그트리

"lazy 세그트리" 자체가 "segment tree with lazy propogation"를 줄여서 부르는 말이기 때문에 propogation이 없다는 것이 다소 이상하기는 하지만, 일부 문제의 경우 세그트리에서 propogation을 lazy하게 하는 것을 넘어서서 아예 하지 않으면 더 효율성을 올릴 수 있다. 시간복잡도는 $O(NlogN)$으로 같다. 

 

이 글에도 같은 내용이 정리되어 있다. 

 

우선 일반적인 lazy 세그트리를 먼저 되짚어보자. 구간 갱신 쿼리와 구간 조회 쿼리(혹은 점 조회 쿼리)가 존재한다. 구간 조회 쿼리에 해당하는 값들을 각 노드에서 들고 있고, $O(logN)$개의 노드를 merge하면 구간 조회 쿼리의 답을 구할 수 있다. 구간 갱신 쿼리는 원래는 $O(N)$개의 노드를 갱신해야 한다. 그러나 깊은 깊이의 노드들은 갱신하지 않고, $O(logN)$개의 노드에서 propogation에 필요한 값들을 들고 있는다. 그리고 이후에 그 노드를 접근할 때 (갱신 쿼리 또는 조회 쿼리) 이를 propogation해준다.

 

이 때, 갱신 쿼리가 commutative(교환법칙이 성립)하다면, propogation을 하지 않아도 된다. 그러면 깊은 깊이의 노드들은 갱신되지 않은 값을 들고 있겠지만, 조회 쿼리 시 재귀가 올라오며 이를 갱신한다. 이 때, 갱신 쿼리가 적용되는 순서가 바뀔 수 있기 때문에 commutative하다는 성질이 있어야 한다. (A[i] <- v 처럼 값을 지정하는 쿼리의 경우에는 commutative하지 않다.) 자세한 내용은 예시를 보자.

 

구간에 수를 더하는 쿼리, 그리고 구간 max 쿼리(RMQ)가 있는 문제를 생각하자. 일반적인 lazy 세그로 아래와 같이 구현할 수 있다.

void propogate(int idx, int l, int r) {
	if(l < r) {
		int m = (l + r) / 2;
		seg[idx * 2] += lazy[idx];
		lazy[idx * 2] += lazy[idx];
		seg[idx * 2 + 1] += lazy[idx];
		lazy[idx * 2 + 1] += lazy[idx];
	}
	lazy[idx] = 0;
}

void updseg(int idx, int l, int r, int x, int y, lint z) {
	if(x <= l && r <= y) {
		lazy[idx] += z;
		seg[idx] += z;
	}
	else if(l <= y && x <= r) {
		int m = (l + r) / 2;
		propogate(idx, l, r);
		updseg(idx * 2, l, m, x, y, z);
		updseg(idx * 2 + 1, m + 1, r, x, y, z);
		seg[idx] = max(seg[idx * 2], seg[idx * 2 + 1]);
	}
}

lint gseg(int idx, int l, int r, int x, int y) {
	if(x <= l && r <= y) return seg[idx];
	if(r < x || y < l) return 0;
	int m = (l + r) / 2;
	propogate(idx, l, r);
	return max(gseg(idx * 2, l, m, x, y), gseg(idx * 2 + 1, m + 1, r, x, y));
}

 

여기에서 propogate 함수를 없애고 updseg와 gseg 함수의 마지막을 아래와 같이 수정해도 정상 작동한다.

propogate 함수가 사라진 대신 연산이 추가되었다. 이 연산이 복잡할 경우 오히려 느려질 수 있으니 적절히 사용하도록 하자.

void updseg(int idx, int l, int r, int x, int y, lint z) {
	...
	else if(l <= y && x <= r) {
		...
		seg[idx] = max(seg[idx * 2], seg[idx * 2 + 1]) + lazy[idx];
	}
}

lint gseg(int idx, int l, int r, int x, int y) {
	...
	return max(gseg(idx * 2, l, m, x, y), gseg(idx * 2 + 1, m + 1, r, x, y)) + lazy[idx];
}