펜윅트리

개념설명
코드

백준 구간합

import java.util.*;
import java.io.*;

public class Main {
	static int N, M, K; 
	static long arr[], tree[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		arr = new long[N+1];
		tree = new long[N+1];
		
		for(int i=1; i<=N; i++) {
			arr[i] = Long.parseLong(br.readLine());
			update(i,arr[i]);
		}
		
		for(int i=0; i<M+K; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(a==1) {
				long c = Long.parseLong(st.nextToken());
				update(b,c-arr[b]);
				arr[b]=c;
			}else if(a==2){
				int c = Integer.parseInt(st.nextToken());
				sb.append((sum(c)-sum(b-1))).append("\n");
			}
			
		}
		System.out.println(sb);
		
	}
	
	static long sum(int i) {
		long sum=0;
		while(i>0) {
			sum += tree[i];
			i -=(i &-i);
		}
		return sum;
	}
	
	static void update(int i, long changeValue) {
		while(i<N+1) {
			tree[i] += changeValue;
			i += (i & -i);
		}
	}
	
}