树状数组

参考资料

• 树状数组 - OI Wiki

实现

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$。
• 计算矩形区域内所有数字的总和。