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

리뷰

 

수열의 특정 구간에 XOR연산을 진행하고, 특정 인덱스의 값을 뽑아 출력하는 문제

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

해당 문제의 심화 버전으로 구간에 xor를 적용하여 출력하는 문제가 있다.

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

 

 

 

전역 변수

• 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)

 

세그먼트 트리를 빌드해 준다. 리프 노드에는 각 수열의 값이, 부모 노드엔 하위 노드끼리 XOR한 값이 초기화 된다.

 

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업데이트를 적용해 준다. 지금 당장 갱신이 필요 없다면 자식 노드에 전파를 해주는 작업을 해준다.

 

4. query

int query(int node, int start, int end, int idx)

 

세그먼트 트리 내의 특정 인덱스의 노드 정보를 출력해 준다. 리프노드까지 도달해야 해서 시간이 좀 걸리는 것 같다.

 

 

문제풀이

1. n값을 입력 받고 길이 n의 수열을 nodes배열에 초기화 해준다.
2. build함수를 통해 nodes배열을 참조하여 tree배열에 세그먼트 트리를 초기화 해준다.
3. m값을 입력 받고 m번의 반복문을 실행해 준 뒤 업데이트 및 쿼리 여부를 order 변수에 입력 받아준다.
4. order가 1이라면 L, R, v를 추가로 입력 받아주고 L ~ R 구간에 v값을 XOR 연산을 통해 업데이트 시켜준다.
5. order가 2라면 index를 추가로 입력 받아주고 수열의 index인 요소를 찾아 출력해준다.

 

참고 사항

XOR연산 특성상 같은 값으로 짝수번 XOR연산을 반복할 경우 자기 자신이 나오게 된다.

따라서 lazy를 처리해 줄때 구간의 길이가 홀수인 경우에만 lazy를 적용해 준다.

 

 

정답 코드

#include<iostream>

using namespace std;
const int MAX_N = 500000;
int nodes[MAX_N];
int tree[MAX_N * 4];
int lazy[MAX_N * 4];
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 idx) {
	propagate(node, start, end);
	if (start == idx && end == idx) return tree[node];
	int mid = (start + end) / 2;
	if (idx <= mid) return query(node * 2, start, mid, idx);
	return query(node * 2 + 1, mid + 1, end, idx);
}

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 order; cin >> order;
		if (order == 1) {
			int L, R, v; cin >> L >> R >> v;
			update(1, 0, n - 1, L, R, v);
		}
		else {
			int index; cin >> index;
			cout << query(1, 0, n - 1, index) << "\n";
		}
	}
}