跳到主要内容

树状数组

参考资料​

实现​

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

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

  • 将某一个数加上 xx；
  • 求出某区间每一个数的和。
洛谷 P3368 【模板】树状数组 2

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

  1. 将某区间每一个数加上 xx；
  2. 求出某一个数的值。
洛谷 P3372 【模板】线段树 1

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

  1. 将某区间每一个数加上 kk。
  2. 求出某区间每一个数的和。
洛谷 P4514 上帝造题的七分钟

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

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