Splay Tree (4) - Lazy Propagation, 구간 뒤집기

안녕하세요.

Splay Tree의 활용 중에서 lazy propagation과 구간 뒤집기에 대해 알아보겠습니다.

splay tree Zig-Zag 연산

---

Lazy Propagation

스플레이 트리로 레이지 프로퍼게이션 또한 가능합니다.

 

Node 구조체

lazy 변수를 추가해 줍니다.

struct Node {
	...
        
	long long lazy;

	...
};

 

Propagation 함수 작성

struct Node {
	...

	void propagate() {
		if (lazy) {
			val += lazy;
			if (l) { l->lazy += lazy; l->sum += lazy * l->cnt; }
			if (r) { r->lazy += lazy; r->sum += lazy * r->cnt; }
		}

		lazy = 0;
	}
};

 

propagation은 자식으로 내려갈 때마다 호출이 되어야 합니다.

=> findKth 함수에 추가해주면 됩니다.

void findKth(int k) {
	Node* x = root;
	while (true) {
		while (x->l && x->l->cnt > k) {
			x = x->l;
			x->propagate();
		}
		if (x->l) k -= x->l->cnt;
		if (!k--) break;
		x = x->r;
		x->propagate();
	}

	splay(x);
}

 

구간 [L, R]에 값 더해주기

먼저, 구간 [L, R]을 추출해 줍니다.

그 후 sum 값과 lazy 값을 업데이트 해줍니다.

void query1(int l, int r, ll v) {
	Node* x = get_range(l, r);
	x->sum += x->cnt * v;
	x->lazy += v;
}

---

구간 뒤집기

splay tree로 구간 뒤집기가 가능합니다.

 

세그먼트 트리로는 빠르게 해당 연산을 수행할 수 없습니다.

하지만 splay tree와 lazy propagation을 사용하면 O(log N) 만에 가능합니다.

 

구간을 뒤집는 것은 왼쪽 서브트리와 오른쪽 서브트리를 바꿔주면 됩니다.

이를 해당 구간이 포함하는 모든 서브트리에 재귀적으로 처리해주면 되는데, 이를 lazy propagation 으로 빠르게 처리할 수 있습니다.

 

Node 구조체

왼쪽 서브트리와 오른쪽 서브트리가 교환됐는지 여부를 나타내는 변수를 하나 추가합니다.

struct Node {
	...
        
	bool _swap;

	...
};

 

Propagation

swap 여부를 전파하는 함수입니다.

struct Node {
	...

	bool _swap;
	
	void push() {
		if (_swap) {
			if (l) l->_swap = !l->_swap;
			if (r) r->_swap = !r->_swap;
			swap(l, r);
			_swap = false;
		}
	}
    
    ...
};

 

구간 뒤집기

구간에 해당하는 부분을 추출한 뒤에 해당 구간의 _swap 변수 값을 바꿔주면 됩니다.

void query(int s, int e) {
	Node *x = range(s, e);
	x->_swap = !x->_swap;
}

---

문제

연습할만한 문제로 아래 2개가 있습니다.

 

https://www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

 

https://www.acmicpc.net/problem/3444

3444번: Robotic Sort

---

참고 자료

https://cubelover.tistory.com/10

Splay Tree