[백준 2042] 구간 합 구하기

(1).인덱스 트리 
#include<iostream>
using namespace std;

int N, M, K;
long long int arr[4000001];
void update(long long int a,long long  int b)
{
	int diff = b - arr[a];
	arr[a] = b;
	a >>= 1;
	while (a)
	{
		arr[a] += diff;
		a >>= 1;
	}
}
long long int hap(long long int a, long long int b)
{
	//cout << a << " " << b << endl;
	long long int sum = 0;
	while (a <= b)
	{
		if (a % 2 == 1) { //홀수일때는 자기자신 더하고 짝수칸으로이동
			sum += arr[a];
		}
		
		if (b % 2 == 0) { // 짝수일때는 자기자신을 더하고 홀수로 이동 
			sum += arr[b];
		}
		a = (a + 1) / 2;
		b = (b - 1) / 2;
	}
	//cout << sum << endl;
	return sum;
}
int main()
{
	scanf("%d %d %d", &N, &M, &K);
	int leaf = 1;
	for (leaf = 1; leaf < N; leaf *= 2);

	for (int i = leaf; i < leaf + N; i++)scanf("%lld", &arr[i]); //리프노드 value 채워주기

	for (int i = leaf - 1; i > 0; i--)
	{
		arr[i] = arr[i * 2] + arr[i * 2 + 1];
	}

	long long int a, b, c;
	for (int i = 0; i < M + K; i++)
	{
		scanf("%lld %lld %lld", &a, &b, &c);
		if (a == 1) //b를 c로 
		{
			update(b+leaf-1, c);
		}
		else
		{
			printf("%lld\n", hap(b+leaf-1,c+leaf-1));
		}
	}
	
}

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

2042번: 구간 합 구하기

 

 

문제분류- 세그먼트 트리