[3일차] 자료구조 D - 2042: 구간 합 구하기

골드 Ⅰ

 

#include <iostream>
using namespace std;

int N, M, K;
long long idxTree[4000001];//인덱스 0 사용안함
int baseNum = 1;

void initTree() {
	int idx = baseNum;

	while (idx /= 2) {
		for (int i = idx; i < idx * 2; i++) {
			int lci = i * 2;
			int rci = lci + 1;
			idxTree[i] = idxTree[lci];
			idxTree[i] += (rci > baseNum + N) ? 0 : idxTree[rci];
		}
	}
}

void updateTree(int idx, long long newNum) {

	//long long 범위 벗어날수도 있어서 delta로 안하고
	//올라가면서 parent마다 새로 계산하는 방식으로 함
	idxTree[idx] = newNum;

	while (idx /= 2) {//인덱스 0에 접근 안 함
		//일단 올라왔음 -> 두 개 봐야함
		int lci = idx * 2;
		int rci = lci + 1;//rci는 N 범위 벗어날 수도 있음
		idxTree[idx] = idxTree[lci];
		idxTree[idx] += (rci > baseNum + N) ? 0 : idxTree[rci];
	}

}

long long partSum(int li, int hi) {
	long long sum = 0;
	while (li <= hi) {
		if (li % 2 == 1) sum += idxTree[li];//li 노드가 rc인 경우 추가
		if (hi % 2 == 0) sum += idxTree[hi];//hi 노드가 lc인 경우 추가
		li = (li + 1) / 2;
		hi = (hi - 1) / 2;
	}
	return sum;
}

int main() {
	scanf("%d%d%d", &N, &M, &K);
	while (baseNum < N) {
		baseNum <<= 1;
	}
	long long num;
	for (int i = baseNum; i < baseNum + N; i++) {
		scanf("%lld", &num);
		idxTree[i] = num;
	}//트리 리프노드 다 채움

	initTree();

	int a, b;//idx 입력받아서 tree 연산 수행
	long long c;//c의 경우 값이 될 수도 있으므로 int 안됨
	for (int i = 0; i < M + K; i++) {
		scanf("%d%d%lld", &a, &b, &c);

		if (a == 1) updateTree(b + baseNum - 1, c);//바꾸기
		else printf("%lld\n", partSum(b + baseNum - 1, c + baseNum - 1));//부분합 계산하여 출력
	}
}

 

인덱스 트리

-> 일단 입력 다 받고! (우선순위 큐와 다른 점)

-> 입력 값들의 변경이 있는 경우 유용!

-> 입력 값들의 (부분적인 무언가)를 구할 때 유용! (빠르다) (부분적인.. 대표값?)

ex) 부분적인 무언가: 부분합, gcd, min, max 어쩌고

 

엑셀에서 수식이 정해져 있는 경우

하나만 바뀌면 관련된 셀들이 다 바뀌는데

딱 그거 생각하면 된다!

 

무언가 정해진 칸들이 있고

거기의 값들이 바뀌면 (관련된 정보가) 자동으로 업데이트가 되는~! ->  O(logn)으로 업데이트 될 거임 트리라 아마 maybe..

ex) 관련된 정보: 부분합, gcd, min, max 어쩌고