개요
-
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
-
출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
접근 방식
-
세그먼트 트리 쪽을 공부하고 접근한 문제이지만, 막상 풀려하니 적용을 못 하겠어서
풀이를 찾아봤다. -
기본적으로 세그먼트 트리는 해당 수열을 리프노드에 다 채워넣고,
재귀를 통해 해당 구간의 합을 부모노드에 갱신하며 채우는 방식이다.
이 문제에선 전체 수 최대값이 100만개이므로 리프노드의 갯수가 100만개가 넘어야한다.
2의 거듭제곱중 100만을 처음 넘기는게 2^20이므로 전체 트리 노드의 갯수는 2^21보다 작다.
따라서 배열의 최대크기를 2^21로 잡는다. -
따라서 완전 이진트리의 첫 리프노드 인덱스를 구하는데,
리프노드의 갯수보다 큰 2의 거듭 제곱수가 해당 인덱스다.int tmp = 1, a = 0, b = 0; long long c = 0; while (tmp<N) { tmp *= 2; } FirstLeafNodeIdx = tmp; -
리프노드에 차례대로 수열을 넣어준다.
//처음 리프노드 위치부터 리프노드들 입력받고 for (int i = 0; i < N; i++) { cin >> Arr[FirstLeafNodeIdx + i]; } -
부모 노드에 해당 노드가 관리하는 수열구간의 합을 저장한다.
주의할 점은 arr[i]= arr[i*2] + arr[i*2+1] 이런식으로 짜야지
arr[i/2]= arr[i]+arr[i+1]로 짜면 안된다.//처음 리프노드 바로전 노드(tmp-1번째 노드)부터 부모노드들 채워나감 for (int i = tmp-1; i > 0; i--) { Arr[i] = Arr[i*2] + Arr[i*2 + 1]; //Arr[i/2] = Arr[i]+Arr[i+1] 을 하면 안됨 \ 리프 두개당 하나가 올라가야되는데(4 5의 부모 2, 6 7 의 부모 3 이런식 )\ 이렇게 짜면 (4 5의 부모 2, 5 6의 부모 2 이런식으로 됨) } -
원소가 바뀌거나 구간합을 출력하는 함수를 ChangeLeafAndReAdjustTree()로 따로 빼줬다.
M+K번 이 함수를 호출하면 된다.
주의할 점은 b값은 index값이므로 b-1값을 매개변수로 넣어줘야한다.
또한 a=2일때 sum함수를 호출할 때, c는 인덱스를 가리키므로 c-1값을 넣어줘야한다.for (int i = 0; i < M + K; i++) { cin >> a >> b >> c; //리프노드 index는 0번째부터 시작하지만 문제에선 1번째부터 라고 표현하므로 b-1번째부터 c번째 ChangeLeafAndReAdjustTree(a, b-1, c); }void ChangeLeafAndReAdjustTree(int a, int b, long long c) { //1일땐 수열 변경과 그에 따른 부모 노드들 변경 if (a == 1) { //b번째는 리프노드 인덱스이므로 리프노드 시작 인덱스 더해야댐 b += FirstLeafNodeIdx; //바꾸려는 값 c에 원래 있던 원소 Arr[b]를 빼줌으로써 두 값의 차이(b번째 원소의 변화량)를 저장 c -= Arr[b]; while (b > 0) { //부모로 거슬러 올라가며 변화량만큼 다 더해줌 Arr[b] += c; b /= 2; } } //2일땐 구간합 출력 else { cout << Sum(b,c-1,1,0,FirstLeafNodeIdx-1)<<'\n'; } } -
구간합을 출력할때는 재귀함수인 Sum함수를 이용한다.
long long Sum(int LTarget, int RTarget, int nodeNum, int LCur, int RCur)인덱스가 nodeNum인 노드가 관리하는 구간이 [LCur, RCur]이고,
우리가 구하길 원하는 구간은 [LTarget,RTarget]이다.
예를들어 루트노드인 nodeNum이 1일땐 관리구간은 모든 리프노드로,
LCur은 0, RCur은 리프노드의 갯수-1이 된다(인덱스 값).각 재귀에서 nodeNum노드가 관리하는 구간이 target구간밖이라면 0을 리턴해주고,
nodeNum노드가 관리하는 구간이 target구간 안이라면 nodeNum노드의 값을 리턴해준다.//현재 Sum함수가 계산하는 범위가 타겟범위를 벗어나면 바로 리턴 0 if (LTarget > RCur || RTarget < LCur) return 0; //현재 Sum함수가 계산하는 범위가 타겟범위 안에 존재하면 LCur부터 RCur값을 담당하는 해당 노드의 값(nodeNum인덱스의 값)을 반환 if (LTarget <= LCur && RCur <= RTarget) return Arr[nodeNum];그 후, 완전 이진트리이므로 자식으로 내려갈때마다
왼쪽 자식 오른쪽 자식으로 쪼개서 재귀를 해준다.//현재 범위가 타겟 범위보다 넓다면 현재범위를 반으로 줄여서 재귀 int mid = (LCur+RCur) / 2; return Sum(LTarget, RTarget, nodeNum * 2, LCur, mid) + Sum(LTarget, RTarget, nodeNum * 2 + 1, mid+1, RCur);
전체 코드
#include<iostream>
using namespace std;
//2^21값이다. 2^20이 100만을 넘어가는 수라서 트리는 높이가 20이 되고, 높이 20의 트리의 총 갯수는 2^21보다 작으므로 최대사이즈를 2^21로 설정
long long Arr[2097152];
int N=0,M=0,K=0,FirstLeafNodeIdx=1;
//LTaget과 RTarget은 우리가 구하려는 타겟 범위,nodeNum은 현재 LCur~RCur구간의 합을 담당하는 노드인덱스 ,LCur, RCur은 현재 범위
long long Sum(int LTarget, int RTarget, int nodeNum, int LCur, int RCur) {
//현재 Sum함수가 계산하는 범위가 타겟범위를 벗어나면 바로 리턴 0
if (LTarget > RCur || RTarget < LCur) return 0;
//현재 Sum함수가 계산하는 범위가 타겟범위 안에 존재하면 LCur부터 RCur값을 담당하는 해당 노드의 값(nodeNum인덱스의 값)을 반환
if (LTarget <= LCur && RCur <= RTarget) return Arr[nodeNum];
//현재 범위가 타겟 범위보다 넓다면 현재범위를 반으로 줄여서 재귀
int mid = (LCur+RCur) / 2;
return Sum(LTarget, RTarget, nodeNum * 2, LCur, mid) + Sum(LTarget, RTarget, nodeNum * 2 + 1, mid+1, RCur);
}
void ChangeLeafAndReAdjustTree(int a, int b, long long c) {
if (a == 1) {
//b번째는 리프노드 인덱스이므로 리프노드 시작 인덱스 더해야댐
b += FirstLeafNodeIdx;
//바꾸려는 값 c에 원래 있던 원소 Arr[b]를 빼줌으로써 두 값의 차이(b번째 원소의 변화량)를 저장
c -= Arr[b];
while (b > 0) {
//부모로 거슬러 올라가며 두값의 차이만큼 다 더해줌
Arr[b] += c;
b /= 2;
}
}
else {
cout << Sum(b,c-1,1,0,FirstLeafNodeIdx-1)<<'\n';
}
}
void Input() {
cin >> N>>M>>K;
int tmp = 1, a = 0, b = 0;
long long c = 0;
while (tmp<N) {
tmp *= 2;
}
FirstLeafNodeIdx = tmp;
//처음 리프노드 위치부터 리프노드들 입력받고
for (int i = 0; i < N; i++) {
cin >> Arr[FirstLeafNodeIdx + i];
}
//처음 리프노드 바로전 노드(tmp-1번째 노드)부터 부모노드들 채워나감
for (int i = tmp-1; i > 0; i--) {
Arr[i] = Arr[i*2] + Arr[i*2 + 1];
//Arr[i/2] = Arr[i]+Arr[i+1] 을 하면 안됨 \
리프 두개당 하나가 올라가야되는데(4 5의 부모 2, 6 7 의 부모 3 이런식 )\
이렇게 짜면 (4 5의 부모 2, 5 6의 부모 2 이런식으로 됨)
}
for (int i = 0; i < M + K; i++) {
cin >> a >> b >> c;
//리프노드 index는 0번째부터 시작하지만 문제에선 1번째부터 라고 표현하므로 b-1번째부터 c번째
ChangeLeafAndReAdjustTree(a, b-1, c);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
}문풀후생
처음에 생각했던 방식으로는 수열이 변화될때마다 수열에 값을 변경한 후
다시 합을 구해서 부모노드들을 구하는 방식으로 생각했었다.
하지만 이 풀이에선 변화량을 저장한 다음,
모든 부모 노드에 해당 변화량만큼만 더해주면 되어서 확실히 편했다.
또한 트리에서 최대노드갯수 설정과
2^k이 1부터 2^k-1을 다 더한 값보다 작다는 부분을 다시 깨닫게 되어서 많은 도움이 되었다.
