Fenwick Tree (펜윅트리)

• 최하위 노드, (idx & -idx)를 빼가며 갱신하고 업데이트하는 간단한 트리, Binary Indexed Tree라고도 함
• 세그먼트 트리의 특징이 담김
• 세그먼트 트리와는 다르게 모든 세그먼트를 만들 필요가 없음
  

최하위 켜져있는 비트 찾기

• idx = (S & -S)
• 10010에서 최하위 켜져있는 비트는 1번째 비트
• 10000에서 최하위 켜져있는 비트는 4번째 비트
• 오른쪽에서부터 탐색을 해서 1을 찾아서 해당 인덱스를 찾는다

  S = 10010, ~S = -(S + 1), 01101 + 1 = -S, 01110 = -S
  => 10010 & 01110 => 00010

Fenwick Tree 수정

• 밑에서 부터 위로

static void update(int[] tree, int i, int dif) {
    while (i < tree.length){
        tree[i] += dif;
        i += (i & -i);
    }
}

Fenwick Tree 구간 합 구하기

• 위에서 아래로

static int sum(int[] tree, int i) {
    int answer = 0;
    while (i > 0){
        answer += tree[i];
        i -= (i & -i);
    }
    return answer;
}

백준 2042 구간 합 구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 *  시간 : 468ms, 메모리 : 109,072KB
 *  펜윅트리
 */
public class Main {
    static int N, M, K;
    static long[] tree;
    static long[] input;
    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());
        tree = new long[N+1];
        input = new long[N+1];
        for (int i = 1; i <= N; i++) {
            input[i] = Long.parseLong(br.readLine());
            update(tree, i, input[i]);
        }
        M += K;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            if (a == 1) {
                int b = Integer.parseInt(st.nextToken());
                long c = Long.parseLong(st.nextToken());
                long dif = c - input[b];
                input[b] = c;
                update(tree, b, dif);
            }else{
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                long totalSum = sum(tree, c) - sum(tree, b-1);
                sb.append(totalSum).append("\n");
            }
        }
        System.out.print(sb);
    }

    private static long sum(long[] tree, int i) {
        long answer = 0;
        while (i > 0){
            answer += tree[i];
            i -= (i & -i);
        }
        return answer;
    }

    private static void update(long[] tree, int i, long dif) {
        while (i < tree.length){
            tree[i] += dif;
            i += (i & -i);
        }
    }
}