펜윅 트리 — 세그먼트 트리보다 간결한 구간 쿼리

// i의 최하위 1비트 값을 구하는 연산
int lowbit(int i) {
    return i & (-i);
}

i = 12 = 1100₂
-i     = 0100₂ (2의 보수)
i & -i = 0100₂ = 4

i = 6  = 0110₂
-i     = 1010₂
i & -i = 0010₂ = 2

i = 7  = 0111₂
-i     = 1001₂
i & -i = 0001₂ = 1

bit[1] = a[1]                     (lowbit(1)=1, 1개)
bit[2] = a[1] + a[2]             (lowbit(2)=2, 2개)
bit[3] = a[3]                     (lowbit(3)=1, 1개)
bit[4] = a[1] + a[2] + a[3] + a[4]  (lowbit(4)=4, 4개)
bit[5] = a[5]                     (lowbit(5)=1, 1개)
bit[6] = a[5] + a[6]             (lowbit(6)=2, 2개)
bit[7] = a[7]                     (lowbit(7)=1, 1개)
bit[8] = a[1] + ... + a[8]       (lowbit(8)=8, 8개)

인덱스:  1    2    3    4    5    6    7    8
         │    │    │    │    │    │    │    │
bit[1] ──┘    │    │    │    │    │    │    │
bit[2] ───────┘    │    │    │    │    │    │
bit[3] ────────────┘    │    │    │    │    │
bit[4] ─────────────────┘    │    │    │    │
bit[5] ──────────────────────┘    │    │    │
bit[6] ───────────────────────────┘    │    │
bit[7] ────────────────────────────────┘    │
bit[8] ─────────────────────────────────────┘

public class FenwickTree {
    private int[] bit;
    private int n;

    public FenwickTree(int n) {
        this.n = n;
        this.bit = new int[n + 1]; // 1-indexed
    }

    // a[i]에 delta를 더함: O(log n)
    public void update(int i, int delta) {
        for (; i <= n; i += i & (-i)) {
            bit[i] += delta;
        }
    }

    // a[1] + a[2] + ... + a[i] 접두사 합: O(log n)
    public int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += bit[i];
        }
        return sum;
    }

    // a[l] + a[l+1] + ... + a[r] 구간 합
    public int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
}

i = 7 (0111₂):  bit[7] 더하기  → i -= lowbit(7)=1 → i=6
i = 6 (0110₂):  bit[6] 더하기  → i -= lowbit(6)=2 → i=4
i = 4 (0100₂):  bit[4] 더하기  → i -= lowbit(4)=4 → i=0
i = 0: 종료

결과: bit[7] + bit[6] + bit[4]
     = a[7] + (a[5]+a[6]) + (a[1]+a[2]+a[3]+a[4])
     = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]

i = 3 (0011₂):  bit[3] += 5  → i += lowbit(3)=1 → i=4
i = 4 (0100₂):  bit[4] += 5  → i += lowbit(4)=4 → i=8
i = 8 (1000₂):  bit[8] += 5  → i += lowbit(8)=8 → i=16
i = 16 > n: 종료

FenwickTree ft = new FenwickTree(n);
for (int i = 1; i <= n; i++) {
    ft.update(i, arr[i]);
}

public FenwickTree(int[] arr) {
    n = arr.length;
    bit = new int[n + 1];

    // 배열 복사
    for (int i = 1; i <= n; i++) {
        bit[i] = arr[i - 1]; // 0-indexed → 1-indexed
    }

    // 부모에게 값 전파
    for (int i = 1; i <= n; i++) {
        int parent = i + (i & (-i));
        if (parent <= n) {
            bit[parent] += bit[i];
        }
    }
}

public long countInversions(int[] arr) {
    int n = arr.length;
    // 좌표 압축 (값의 범위를 1~n으로)
    int[] sorted = arr.clone();
    Arrays.sort(sorted);
    Map<Integer, Integer> rank = new HashMap<>();
    for (int i = 0; i < n; i++) {
        rank.put(sorted[i], i + 1);
    }

    FenwickTree ft = new FenwickTree(n);
    long inversions = 0;

    // 뒤에서부터 순회
    for (int i = n - 1; i >= 0; i--) {
        int r = rank.get(arr[i]);
        // 현재 값보다 작은 값 중 이미 등장한 것의 수
        inversions += ft.query(r - 1);
        ft.update(r, 1);
    }

    return inversions;
}

public class FenwickTree2D {
    private int[][] bit;
    private int rows, cols;

    public FenwickTree2D(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.bit = new int[rows + 1][cols + 1];
    }

    public void update(int r, int c, int delta) {
        for (int i = r; i <= rows; i += i & (-i)) {
            for (int j = c; j <= cols; j += j & (-j)) {
                bit[i][j] += delta;
            }
        }
    }

    public int query(int r, int c) {
        int sum = 0;
        for (int i = r; i > 0; i -= i & (-i)) {
            for (int j = c; j > 0; j -= j & (-j)) {
                sum += bit[i][j];
            }
        }
        return sum;
    }
}