12. 세그먼트트리-Fenwick

세그먼트 트리 / Fenwick Tree

Summary

값이 바뀌지 않으면 누적합, 값이 바뀌면 Fenwick 또는 Segment Tree다.
구간합 + 점 업데이트는 Fenwick이 짧고, 다양한 구간 연산은 Segment Tree가 낫다.

---

선택 기준

상황	추천
구간합 질의만 있음	누적합
점 업데이트 + 구간합	Fenwick Tree
구간 최솟값/최댓값	Segment Tree
다양한 구간 연산	Segment Tree

---

Segment Tree 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    static int n;
    static long[] arr;
    static long[] tree;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
 
        arr = new long[n + 1];
        tree = new long[n * 4];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
 
        build(1, 1, n);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            int a = Integer.parseInt(st.nextToken());
            long b = Long.parseLong(st.nextToken());
 
            if (op.equals("sum")) {
                sb.append(query(1, 1, n, a, (int) b)).append('\n');
            } else if (op.equals("update")) {
                update(1, 1, n, a, b);
            }
        }
 
        System.out.print(sb);
    }
 
    static void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
 
        int mid = (start + end) / 2;
        build(node * 2, start, mid);
        build(node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
 
    static long query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return 0;
        if (left <= start && end <= right) return tree[node];
 
        int mid = (start + end) / 2;
        return query(node * 2, start, mid, left, right)
             + query(node * 2 + 1, mid + 1, end, left, right);
    }
 
    static void update(int node, int start, int end, int index, long value) {
        if (start == end) {
            tree[node] = value;
            return;
        }
 
        int mid = (start + end) / 2;
        if (index <= mid) update(node * 2, start, mid, index, value);
        else update(node * 2 + 1, mid + 1, end, index, value);
 
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

---

Fenwick Tree 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    static int n;
    static long[] tree;
    static long[] arr;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
 
        tree = new long[n + 1];
        arr = new long[n + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            add(i, arr[i]);
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            int a = Integer.parseInt(st.nextToken());
            long b = Long.parseLong(st.nextToken());
 
            if (op.equals("sum")) {
                sb.append(rangeSum(a, (int) b)).append('\n');
            } else if (op.equals("update")) {
                long diff = b - arr[a];
                arr[a] = b;
                add(a, diff);
            }
        }
 
        System.out.print(sb);
    }
 
    static void add(int index, long value) {
        while (index <= n) {
            tree[index] += value;
            index += index & -index;
        }
    }
 
    static long prefixSum(int index) {
        long sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }
 
    static long rangeSum(int left, int right) {
        return prefixSum(right) - prefixSum(left - 1);
    }
}

---

주의점

인덱스는 보통 1-indexed로 둔다.
합은 long으로 둔다.
Fenwick의 index += index & -index 방향을 외운다.
Segment Tree 배열은 보통 4 * N 크기로 잡는다.

---

백지 복원

1. 값 변경이 없으면 굳이 세그트리를 쓰지 않는 이유는?
2. Fenwick에서 prefixSum의 index 이동식은?
3. Segment Tree query에서 범위가 안 겹치면 무엇을 반환하는가?