BIT(페니크 트리) 개요

BIT(Binary Indexed Tree)는 구간 합을 빠르게 계산하고, 특정 인덱스의 값을 업데이트할 수 있는 자료구조입니다. lowbit 연산을 기반으로 하여 시간 복잡도 O(log N)을 보장합니다.

P3374: 기본적인 BIT 연산

단일 값 갱신과 구간 합을 처리하는 가장 기초적인 템플릿 문제입니다.

#include <bits/stdc++.h>
using namespace std;
int n, m, bit[2000010];

int lowbit(int x) {
    return x & -x;
}

void update(int pos, int val) {
    for (int i = pos; i <= n; i += lowbit(i))
        bit[i] += val;
}

int query(int pos) {
    int res = 0;
    for (int i = pos; i > 0; i -= lowbit(i))
        res += bit[i];
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int val; cin >> val;
        update(i, val);
    }
    while (m--) {
        int cmd, a, b; cin >> cmd >> a >> b;
        if (cmd == 1) 
            update(a, b);
        else 
            cout << query(b) - query(a - 1) << '\n';
    }
    return 0;
}

P3368: 구간 갱신 단일 조회

차분 배열(Difference Array)을 BIT로 관리하여, 구간 갱신과 단일 값 조회를 처리합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, q, bit[500001], init[500001];

ll lowbit(ll x) { return x & -x; }

void add(ll pos, ll val) {
    for (ll i = pos; i <= n; i += lowbit(i)) 
        bit[i] += val;
}

ll sum(ll pos) {
    ll ret = 0;
    for (ll i = pos; i > 0; i -= lowbit(i))
        ret += bit[i];
    return ret;
}

int main() {
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &init[i]);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            ll l, r, v;
            scanf("%lld%lld%lld", &l, &r, &v);
            add(l, v);
            add(r + 1, -v);
        } else {
            ll pos; scanf("%lld", &pos);
            printf("%lld\n", init[pos] + sum(pos));
        }
    }
    return 0;
}

P2344: DP + BIT를 활용한 최적화

동적 계획법(DP)에서 점화식이 특정 조건(부분합 비교)을 만족할 때, BIT를 사용하여 O(N log N)으로 최적화합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 9;
int n, bit[100005];
ll arr[100005], pref[100005], dp[100005];
vector<ll> comp;

void insert(int idx, ll val) {
    for (int i = idx + 1; i <= n + 1; i += i & -i) {
        bit[i] = (bit[i] + val) % MOD;
    }
}

ll query(int idx) {
    ll res = 0;
    for (int i = idx + 1; i > 0; i -= i & -i)
        res = (res + bit[i]) % MOD;
    return res;
}

int main() {
    cin >> n;
    comp.push_back(0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        pref[i] = pref[i - 1] + arr[i];
        comp.push_back(pref[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    auto get_idx = [&](ll v) {
        return lower_bound(comp.begin(), comp.end(), v) - comp.begin();
    };

    dp[get_idx(0)] = 1;
    insert(get_idx(0), 1);

    for (int i = 1; i <= n; i++) {
        dp[i] = query(get_idx(pref[i]));
        insert(get_idx(pref[i]), dp[i]);
    }
    cout << dp[n] << '\n';
    return 0;
}

P6186: 버블 정렬과 BIT

각 원소의 역전 개수( inversion count )를 관리하며, 버블 정렬의 각 패스마다 역전 개수가 변화하는 것을 BIT로 추적합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 500005;
int n, m, arr[N], inv[N];

struct BIT {
    ll tree[N];
    void add(int x, ll v) {
        for (int i = x + 1; i < N; i += i & -i) tree[i] += v;
    }
    ll sum(int x) {
        ll res = 0;
        for (int i = x + 1; i > 0; i -= i & -i) res += tree[i];
        return res;
    }
} cnt_bit, val_bit;

void modify(int idx, ll delta) {
    cnt_bit.add(idx, delta);
    val_bit.add(idx, idx * delta);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        inv[i] = cnt_bit.sum(n) - cnt_bit.sum(arr[i]);
        cnt_bit.add(arr[i], 1);
    }
    memset(&cnt_bit, 0, sizeof(cnt_bit));
    for (int i = 1; i <= n; i++) modify(inv[i], 1);

    while (m--) {
        int op, x; cin >> op >> x;
        if (op == 1) {
            modify(inv[x], -1);
            modify(inv[x + 1], -1);
            if (arr[x] < arr[x + 1]) {
                inv[x] = inv[x + 1];
                inv[x + 1] = inv[x] + 1;
            } else {
                inv[x] = inv[x + 1] - 1;
                inv[x + 1] = inv[x];
            }
            modify(inv[x], 1);
            modify(inv[x + 1], 1);
            swap(arr[x], arr[x + 1]);
        } else {
            if (x >= n) {
                cout << 0 << '\n';
                continue;
            }
            ll total = val_bit.sum(n) - val_bit.sum(x - 1);
            ll cnt = cnt_bit.sum(n) - cnt_bit.sum(x - 1);
            cout << max(0LL, total - cnt * x) << '\n';
        }
    }
    return 0;
}

P6619: 이분 탐색과 BIT

얼음과 불의 두 그룹에 대해 BIT 두 개를 사용합니다. 특정 값 k를 기준으로 온도 조건을 만족하는 에너지 최댓값을 이분 탐색으로 찾습니다.

#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
int tot;
struct BIT {
    int tree[N];
    void add(int x, int v) {
        for (int i = x + 1; i < N; i += i & -i) tree[i] += v;
    }
    int sum(int x) {
        int res = 0;
        for (int i = x + 1; i > 0; i -= i & -i) res += tree[i];
        return res;
    }
} ice, fire;

struct Query {
    int op, t, x, y;
} q[N];
int comp[N], qcnt;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int qry; cin >> qry;
    for (int i = 1; i <= qry; i++) {
        cin >> q[i].op >> q[i].t;
        if (q[i].op == 1) {
            cin >> q[i].x >> q[i].y;
            comp[++qcnt] = q[i].x;
        }
    }
    sort(comp + 1, comp + 1 + qcnt);
    tot = unique(comp + 1, comp + 1 + qcnt) - comp - 1;
    for (int i = 1; i <= qry; i++)
        if (q[i].op == 1)
            q[i].x = lower_bound(comp + 1, comp + 1 + tot, q[i].x) - comp;

    for (int i = 1; i <= qry; i++) {
        if (q[i].op == 1) {
            if (q[i].t == 0) ice.add(q[i].x, q[i].y);
            else fire.add(q[i].x, q[i].y);
        } else {
            int idx = q[i].t;
            if (q[idx].t == 0) ice.add(q[idx].x, -q[idx].y);
            else fire.add(q[idx].x, -q[idx].y);
        }

        int lo = 1, hi = tot, pos1 = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (ice.sum(mid) <= fire.sum(tot) - fire.sum(mid - 1)) {
                pos1 = mid;
                lo = mid + 1;
            } else hi = mid - 1;
        }

        int val_ice = ice.sum(pos1);
        int val_fire = fire.sum(tot) - fire.sum(pos1);
        int pos2 = pos1;
        lo = pos1 + 1; hi = tot;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (fire.sum(mid) - fire.sum(pos1) == 0) {
                pos2 = mid;
                lo = mid + 1;
            } else hi = mid - 1;
        }
        pos2++;

        int best = max(val_ice, val_fire);
        if (best == 0) {
            cout << "Peace\n";
            continue;
        }
        if (val_ice <= val_fire)
            cout << comp[pos2] << ' ' << 2 * val_fire << '\n';
        else
            cout << comp[pos1] << ' ' << 2 * val_ice << '\n';
    }
    return 0;
}