인덱스 트리

2042번: 구간 합 구하기 (acmicpc.net)

2042번: 구간 합 구하기

#if 01

#include <iostream>
#include <string.h>

using namespace std;

long long arr[1000001], tree[1000001];
int n, m, k;	// 데이터 갯수, 변경 횟수, 구간합 계산 횟수


// i번째 수까지의 누적 합을 계산하는 함수
// 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합 계산
long long prefixSum(int i) {
	long long result = 0;
	while (i > 0) {
		result += tree[i];
		i -= (i & -i);
	}
	return result;
}

// i번째 수를 dif만큼 더하는 함수
// 0이 아닌 마지막 비트만큼 더하면서 구간들의 값 변경
void update(int i, long long dif) {
	while (i <= n) {
		tree[i] += dif;
		i += (i & -i);
	}
}

long long intervalSum(int start, int end) {
	return prefixSum(end) - prefixSum(start - 1);
}


int main(void) {
	memset(tree, 0, sizeof(tree));

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		long long x;
		cin >> x;
		arr[i] = x;
		update(i, x);
	}

	int cnt = 0;
	while (cnt++ < m + k) {
		int op;
		cin >> op;
		if (op == 1) {
			int index;
			long long value;
			cin >> index >> value;
			update(index, value - arr[index]);
			arr[index] = value;
		}
		else {
			int start, end;
			cin >> start >> end;
			cout << intervalSum(start, end);
		}
	}
}


# endif