树状数组

Question

用一个数据结构维护一个序列，支持单点修改和区间求和。

Algorithm：树状数组

前置知识：lowbit

用来计算一个数二进制下的最低位的1和后面的0构成的数。计算方法为：\(\text{lowbit}(x)=x\&(-x)\)

例如 \(\text{lowbit}(14)=2\):

   1 1 1 0---- 14
 & 0 0 1 0---- -14
------------------
 = 0 0 1 0---- 2

正文：

观察这个树状数组，可以得到：

\[\begin{aligned} c_1&=a_1\\ c_2&=a_1+a_2=c_1+a_2 \\ c_3&=a_3\\ c_4&=a_1+a_2+a_3+a_4=c_2+c_3+a_4 \\ c_5&=a_5 \\ c_6&=a_5+a_6=c_5+a_6\\ c_7&=a_7 \\ c_8&=\sum\limits_{i=1}^8 a_i= c_4+c_6+c_7+a_8\\ \end{aligned} \]

再观察这个树状数组，可以发现：

• 树状数组中某个节点 \(i\) 的父节点的下标为 \(i+\text{lowbit(i)}\) 。

  由此可知单点修改的方法为：沿着父节点一路向上爬，直到更新完整个区间。

  复杂度为 \(O(n*log_2(n))\)。

• 树状数组中某个节点 \(i\) 的左兄弟下标为 \(i-\text{lowbit(i)}\)

  由此可知查询前缀和的方法为：从最右边的端点开始一直爬左兄弟进行累计。

  复杂度为 \(O(n*log_2(n))\)。

Code

\(\text{lowbit}\):

ll lowbit(int x){return x&(-x);}

修改：

void update(int x,int y){
	while(x<=n){
		c[x]+=y;
		x+=lowbit(x);
	}
}

查询：

ll query(ll x){
	ll sum=0;
	while(x){
		sum+=y;
		x-=lowbit(x);
	}
	return sum;
}

Examples

Reference

jijidawang'blog

算法竞赛进阶指南——李煜东

学校课件