树状数组（Binary Indexed Tree）

特点

树状数组常用于查询前缀和，前缀和通过差分可以得到区间和，并支持单点修改 单点修改和查询前缀和的时间复杂度均为\(O(n\log_2 n)\)

数据结构与基本操作

假定有\(a_1, a_2, ..., a_n\)共n个数，我们使用数组bit[n+1] = {0}, 其中0位置不存储任何信息，仅作为边界判断

i最低位的2的幂

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

前缀和

int sum(int i){ int r = 0; while(i > 0){ r += bit[i]; i -= lowbit(i) } return r; }

单点修改

void update(int i, int d){ while(i <= n){ bit[i] += d; i += lowbit(i) } }

初始化

for(int i = 0; i < a.size(); i++) update(i + 1, a[i]);

经典例题

模板题

307. Range Sum Query - Mutable493. Reverse Pairs

离散化

315. Count of Smaller Numbers After Self327. Count of Range Sum

参考

topcoder BIT

转载于:https://www.cnblogs.com/qbits/p/10972651.html