树状数组

abensyl · 2023-07-17 20:17:18 · 个人记录

树状数组合集 - sto_5k_orz

简介

树状数组或二叉索引树（Binary Indexed Tree），又以其发明者命名为 Fenwick 树，最早由 Peter M. Fenwick 于 1994 年为题发表的。其初衷是解决数据压缩里的累积频率的计算问题，现多用于高效计算数列的前缀和、区间和。

代码

lowbit 与数组声明

#define lowbit(i) i&-i
const int N = 1e6+5;
int bit[N];

update

void update(int a, int b) {
    for (int i = a; i < N; i += i & -i)
        bit[i] += b;
}

query

int query(int a) {
    int res = 0;
    for (int i = a; i; i -= i & -i)
        res += bit[i];
    return res;
}

练习题：

HH 的项链：提示与详解
乌鸦喝水：提示与详解