Algorithm in A..Z - Fenwick Tree(Binary Indexed Tree)

개념

각 인덱스는 최하위 비트의 값만큼 구간을 저장하고 이를 이용하여 구간의 합을 빠르게 찾을 수 있다.

=> 1, 3, 5, 7은 최하위 비트의 값이 1 -> 구간의 길이가 1만큼의 합을 저장

=> 2, 6은 최하위 비트의 값이 2 -> 구간의 길이가 2만큼의 합을 저장

=> 4는 최하위 비트의 값이 4 -> 구간의 길이가 4만큼의 합을 저장

=> 8은 최하위 비트의 값이 8 -> 구간의 길이가 8만큼 합을 저장

---

작동원리

 

최하위 비트를 구하는 법

index & -index

 

 

Query

1-3 구간의 합을 구하면 트리에서 2, 3을 더한다.

1. 3(0011)에 저장된 값을 더하고 최하위 비트(0001)를 뺀다. => 2(0010)
2. 2(0010)에 저장된 값을 더하고 최하위 비트(0010)를 뺀다. => 0(0000)
3. 0이면 종료한다.

1-7 구간의 합을 구하면 트리에서 4, 6, 7을 더한다.

1. 7(0111)에 저장된 값을 더하고 최하위 비트(0001)를 뺀다. => 6(0110)
2. 6(0110)에 저장된 값을 더하고 최하위 비트(0010)를 뺀다. => 4(0100)
3. 4(0100)에 저장된 값을 더하고 최하위 비트(0100)를 뺀다. => 0(0000)
4. 0이면 종료한다.

4-7 구간의 합을 구하려면 1-7까지 구간의 합과 1-3까지 구간의 합을 빼서 구한다.

 

Update

1의 인덱스 값을 변경하면 1, 2, 4, 8의 값을 Update한다.

1. 1(0001)의 인덱스 값을 Update하고 최하위 비트(0001)를 더한다. => 2(0010)
2. 2(0010)의 인덱스 값을 Update하고 최하위 비트(0010)를 더한다. => 4(0100)
3. 4(0100)의 인덱스 값을 Update하고 최하위 비트(0100)를 더한다. => 8(1000)
4. 8(1000)의 인덱스 값을 Update하고 최하위 비트(1000)를 더한다. => 16
5. 16은 Tree의 Index를 벗어아니까 종료한다.

3의 인덱스 값을 변경하면 3, 4, 8의 값을 Update한다. 

1. 3(0011)의 인덱스 값을 Update하고 최하위 비트(0001)를 더한다. => 4(0010)
2. 4(0100)의 인덱스 값을 Update하고 최하위 비트(0100)를 더한다. => 8(1000)
3. 8(1000)의 인덱스 값을 Update하고 최하위 비트(1000)를 더한다. => 16
4. 16은 Tree의 Index를 벗어아니까 종료한다.

---

시간 복잡도

Query => O(logN)

Update => O(logN)

---

문제

www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

---

코드

#include <bits/stdc++.h>
using namespace std;

vector<long long> ve, tree;
void update(int index, long long diff) {
    while (index < tree.size()) {
        tree[index] += diff;
        index += (index & -index);
    }
}

long long query(int index) {
    long long result = 0L;
    while (index > 0) {
        result += tree[index];
        index -= (index & -index);
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    ve.resize(n + 1);
    tree.resize(n + 1);
    for (int i = 1;i <= n;++i) {
        cin >> ve[i];
        update(i, ve[i]);
    }

    for (int i = 0;i < m  + k;++i) {
        int a;
        cin >> a;

        if (a == 1) {
            int b;
            long long c;
            cin >> b >> c;

            update(b, c - ve[b]);
            ve[b] = c;
        } else {
            int b, c;
            cin >> b >> c;
            
            cout << query(c) - query(b - 1) << "\n";
        }
    }
}