[C++] indexed tree / 백준 2042번

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

2042번: 구간 합 구하기

#include <bits/stdc++.h>

using namespace std;

// 전체 데이터의 개수는 최대 1,000,000개
long long arr[1000001], tree[1000001];
// 데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k)
int n, m, k;

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

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()
{
	int i;
	cin >> n >> m >> k;

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

	int count = 0;
	while (count++ < m + k) {
		int op;
		cin >> op;
		// update 
		if (op == 1) {
			int index;
			long long v;
			cin >> index >> v;
			update(index, v - arr[index]);
			arr[index] = v;	// i번째 수를 value로 업데이트
		}
		// interval sum
		else {
			int start, end;
			cin >> start >> end;
			cout << intervalSum(start, end) << endl;
		}
	}

	return 0;
}