树状数组

参考资料

• 树状数组 - OI Wiki

简介

树状数组（Binary Indexed Tree，BIT），又称 Fenwick 树，用 $O(\log n)$ 维护前缀信息并支持单点修改。借助 lowbit(x)=x&-x，节点 $c_x$ 维护区间 $(x-\operatorname{lowbit}(x),x]$ 的聚合值。修改时沿 $x\to x+\operatorname{lowbit}(x)$ 上跳，查询前缀时沿 $x\to x-\operatorname{lowbit}(x)$ 下跳，单次操作 $O(\log n)$。它实现简洁、常数小，适合维护前缀和、区间和等可差分的信息。

实现

146 Bcpp

struct BIT
{
	int c[N];
	void add(int u,int v){while(u<N){c[u]+=v;u+=u&-u;}}
	int sum(int u){int res=0;while(u){res+=c[u];u-=u&-u;}return res;}
};

例题

洛谷 P3374 【模板】树状数组 1

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 $x$；
• 求出某区间每一个数的和。

洛谷 P3368 【模板】树状数组 2

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $x$；
2. 求出某一个数的值。

洛谷 P3372 【模板】线段树 1

如题，已知一个数列 $\{a_i\}$，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

洛谷 P4514 上帝造题的七分钟

维护一个二维矩阵，需要支持以下两种操作：

• 将矩形区域内的所有数字增加 $v$。
• 计算矩形区域内所有数字的总和。