[P3] 백준 12844번 XOR C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰

 

XOR연산에 대해 재정립 하는 시간이 되었다.

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

 

전역 변수

• MAX_N : 노드의 최대 개수를 저장할 인트형 상수 정수, 50만으로 초기화 해준다.
• nodes : 노드의 정보를 저장할 정수형 배열, MAX_N크기로 초기화 한다.
• tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.
• lazy : 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.
• n, m : 노드의 개수를 저장할 정수 변수 n, 쿼리의 개수를 저장할 정수 변수 m

 

함수

1. build

void build(int node, int start, int end)

 

세그먼트 트리를 초기화 해주는 함수

 

2. propagate

void propagate(int node, int start, int end)

 

저장된 갱신 정보가 있다면 실행해 주고, 하위 노드에 갱신 정보를 전파해 주는 함수

 

3. update

void update(int node, int start, int end, int L, int R, int val)

 

주어진 구간에 val을 업데이트 값으로 넘겨주는 함수, lazy에 val을 전달해 주고 propagate를 통해 업데이트를 진행해 주는 형식이며 적용된 업데이트를 세그먼트 트리에 반영해 준다.

 

4. query

int query(int node, int start, int end, int L, int R)

 

주어진 구간에 존재하는 모든 노드의 값을 xor연산을 통해 출력해 주는 함수

 

 

문제풀이

1. n값을 입력 받고, nodes배열에 n개의 노드 정보를 입력받아 준다.
2. build 함수를 통해 nodes배열에 저장된 노드의 값으로 세그먼트 트리를 초기화 해준다.
3. m값을 입력 받고, m개의 쿼리를 실행해 준다. a, b, c에 적용할 쿼리의 종류, 범위를 받아와 준다.
4. a가 1일 경우 d를 추가로 입력 받아주고 b ~ c범위에 d값을 xor연산하여 업데이트를 실행한다.
5. a가 2일 경우 범위내 값을 모두 xor연산하여 결과를 리턴 후 출력해 준다.

 

참고 사항

업데이트의 구간이 짝수이면 xor연산을 적용할 경우 하위 노드의 값만 변경되어야 한다.

하위 노드 값에 xor 연산이 되어도 상위 노드의 값은 변하지 않기 때문이다.

 

1. 5, 6 두개의 노드에 4를 업데이트 한다고 가정하면 1, 2가 된다.
2. 5, 6을 xor연산하면 3이고 1, 2를 xor연산하면 3이다. 값이 동일함을 알 수 있다.
3. 11, 19 두개의 노드에 3을 업데이트 한다고 가정하면 8, 16이 된다.
4. 11, 19를 xor연산하면 24고 8, 16을 xor연산하면 24이다. 값이 동일함을 알 수 있다.
5. 따라서, 구간이 짝수일때 xor연산을 진행해 준다면 원하는 값이 나오지 않는다.

 

정답 코드

#include<iostream>

using namespace std;

const int MAX_N = 500000;
int nodes[MAX_N];
int tree[MAX_N * 4];
int lazy[MAX_N * 4] = { 0, };
int n, m;

void build(int node, int start, int end) {
	if (start == end) tree[node] = nodes[start];
	else {
		int mid = (start + end) / 2;
		build(node * 2, start, mid);
		build(node * 2 + 1, mid + 1, end);
		tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
	}
}

void propagate(int node, int start, int end) {
	if (lazy[node]) {
		if ((end - start + 1) % 2) tree[node] ^= lazy[node];
		if (start != end) {
			lazy[node * 2] ^= lazy[node];
			lazy[node * 2 + 1] ^= lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int node, int start, int end, int L, int R, int val) {
	propagate(node, start, end);
	if (R < start || end < L) return;
	if (L <= start && end <= R) {
		lazy[node] ^= val;
		propagate(node, start, end);
		return;
	}
	int mid = (start + end) / 2;
	update(node * 2, start, mid, L, R, val);
	update(node * 2 + 1, mid + 1, end, L, R , val);
	tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
}

int query(int node, int start, int end, int L, int R) {
	propagate(node, start, end);
	if (R < start || end < L) return 0 ;
	if (L <= start && end <= R) return tree[node];
	int mid = (start + end) / 2;
	int left = query(node * 2, start, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, end, L, R);
	return left ^ right;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> nodes[i];
	build(1, 0, n - 1);
	cin >> m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		if (a == 1) {
			int d; cin >> d;
			update(1, 0, n - 1, b, c, d);
		}
		else cout << query(1, 0, n - 1, b, c) << "\n";
	}
}