树状数组板子

r囧r小猫 2022-03-15 15:22 276阅读 0赞

树状数组  重点是在**树状**的数组

大家都知道二叉树吧

叶子结点代表A数组A\[1\]~A\[8\]

![786945-20161206222443741-1201716038.png][]

现在变形一下

![786945-20161206222444069-504520694.png][]

现在定义每一列的顶端结点C\[\]数组

如下图

![786945-20161206222444319-1066528329.jpg][]

C\[i\]代表 子树的叶子结点的权值之和// **这里以求和举例**

如图可以知道

C\[1\]=A\[1\];

C\[2\]=A\[1\]+A\[2\];

C\[3\]=A\[3\];

C\[4\]=A\[1\]+A\[2\]+A\[3\]+A\[4\];

C\[5\]=A\[5\];

C\[6\]=A\[5\]+A\[6\];

C\[7\]=A\[7\];

C\[8\]=A\[1\]+A\[2\]+A\[3\]+A\[4\]+A\[5\]+A\[6\]+A\[7\]+A\[8\];

下面观察如下图

![786945-20161206222444679-518511660.png][]

将C\[\]数组的结点序号转化为**二进制**

1=(001)      C\[1\]=A\[1\];

2=(010)      C\[2\]=A\[1\]+A\[2\];

3=(011)      C\[3\]=A\[3\];

4=(100)      C\[4\]=A\[1\]+A\[2\]+A\[3\]+A\[4\];

5=(101)      C\[5\]=A\[5\];

6=(110)      C\[6\]=A\[5\]+A\[6\];

7=(111)      C\[7\]=A\[7\];

8=(1000)    C\[8\]=A\[1\]+A\[2\]+A\[3\]+A\[4\]+A\[5\]+A\[6\]+A\[7\]+A\[8\];

对照式子可以发现  **C\[i\]=A\[i-2^k+1\]+A\[i-2^k+2\]+......A\[i\]; （k为i的二进制中从最低位到高位连续零的长度）例如i=8时，k=3;**

可以自行带入验证;

现在引入lowbit(x)

lowbit(x) 其实就是取出x的最低位1  换言之**  lowbit(x)=2^k  k的含义与上面相同 理解一下**

下面说代码

1.  `int lowbit(int t)`
2.  `{`
3.  `return t&(-t);`
4.  `}`
5.  `//-t 代表t的负数 计算机中负数使用对应的正数的补码来表示`
6.  `//例如 :`
7.  `// t=6（0110） 此时 k=1`
8.  `//-t=-6=(1001+1)=(1010)`
9.  `// t&(-t)=(0010)=2=2^1`

**C\[i\]=A\[i-2^k+1\]+A\[i-2^k+2\]+......A\[i\];**

**C\[i\]=****A\[i-lowbit(i)+1\]+A\[i-lowbit(i)+2\]+......A\[i\];**

** **

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*分割线

**区间查询**

ok 下面利用C\[i\]数组，求A数组中前i项的和

举个例子 i=7;

sum\[7\]=A\[1\]+A\[2\]+A\[3\]+A\[4\]+A\[5\]+A\[6\]+A\[7\] ;   前i项和

C\[4\]=A\[1\]+A\[2\]+A\[3\]+A\[4\];   C\[6\]=A\[5\]+A\[6\];   C\[7\]=A\[7\];

可以推出:   sum\[7\]=C\[4\]+C\[6\]+C\[7\];

序号写为二进制: sum\[(111)\]=C\[(100)\]+C\[(110)\]+C\[(111)\];

再举个例子 i=5

sum\[5\]=A\[1\]+A\[2\]+A\[3\]+A\[4\]+A\[5\] ;   前i项和

C\[4\]=A\[1\]+A\[2\]+A\[3\]+A\[4\];   C\[5\]=A\[5\];

可以推出:   sum\[5\]=C\[4\]+C\[5\];

序号写为二进制: sum\[(101)\]=C\[(100)\]+C\[(101)\];

**细细观察二进制 树状数组追其根本就是二进制的应用**

结合代码

1.  `int getsum(int x)`
2.  `{`
3.  `int ans=0;`
4.  `for(int i=x;i>0;i-=lowbit(i))`
5.  `ans+=C[i];`
6.  `return ans；`
7.  `}`

对于i=7 进行演示

7(111)     **     ans+=C\[7\]**

lowbit(7)=001  7-lowbit(7)=6(110) **   ans+=C\[6\]**

lowbit(6)=010  6-lowbit(6)=4(100)    **ans+=C\[4\]**

lowbit(4)=100  4-lowbit(4)=0(000)

对于i=5 进行演示

5(101)     **      ans+=C\[5\]**

lowbit(5)=001  5-lowbit(5)=4(100) **   ans+=C\[4\]**

lowbit(4)=100  4-lowbit(4)=0(000)

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*分割线

**单点更新**

当我们修改A\[\]数组中的某一个值时  应当如何更新C\[\]数组呢？

回想一下 区间查询的过程，再看一下上文中列出的图

结合代码分析

1.  `void add(int x,int y)`
2.  `{`
3.  `for(int i=x;i<=n;i+=lowbit(i))`
4.  `tree[i]+=y;`
5.  `}`
6.  `//可以发现 更新过程是查询过程的逆过程`
7.  `//由叶子结点向上更新C[]数组`

![786945-20161206222445132-1538640594.jpg][]

如图：

当更新A\[1\]时  需要向上更新C\[1\] ,C\[2\],C\[4\],C\[8\]

C\[1\],   C\[2\],    C\[4\],     C\[8\]

写为二进制  C\[(001)\],C\[(010)\],C\[(100)\],C\[(1000)\]

1(001)        **C\[1\]+=A\[1\]**

lowbit(1)=001 1+lowbit(1)=2(010)     **C\[2\]+=A\[1\]**

lowbit(2)=010 2+lowbit(2)=4(100)     **C\[4\]****+=A\[1\]**

lowbit(4)=100 4+lowbit(4)=8(1000)   **C\[8\]****+=A\[1\]**

**洛谷3374模板**

## 题目描述 ##

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

1.将某一个数加上x

2.求出某区间每一个数的和

## 输入输出格式 ##

**输入格式：**

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1： 格式：1 x k 含义：将第x个数加上k

操作2： 格式：2 x y 含义：输出区间\[x,y\]内每个数的和

**输出格式：**

输出包含若干行整数，即为所有操作2的结果。

## 输入输出样例 ##

**输入样例\#1：** 复制

5 5
    1 5 4 2 3
    1 1 3
    2 2 5
    1 3 -1
    1 4 2
    2 1 4

**输出样例\#1：** 复制

14
    16

#include<bits/stdc++.h>
    using namespace std;
    int d[500005],tree[2000005],n,m;
    int lowbit(int i){
    	return i&-i;
    }
    void add(int x,int v){
    	while(x<=n){
    		tree[x]+=v;
    		x+=lowbit(x);
    	}
    }
    int sum(int x){
    	int ans=0;
    	while(x!=0){
    		ans+=tree[x];
    		x-=lowbit(x);
    	}
    	return ans;
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		scanf("%d",&d[i]); 
    		add(i,d[i]);
    	}
    	int a,b,c;
    	for(int i=1;i<=m;i++){
    		scanf("%d%d%d",&a,&b,&c);
    		if(a==1)add(b,c);
    		else printf("%d\n",sum(c)-sum(b-1));
    	}
    	return 0;
    }

[786945-20161206222443741-1201716038.png]: /images/20220315/18608696049a43ca9ed51acbf37f9821.png
[786945-20161206222444069-504520694.png]: /images/20220315/d92b8b0af55a401e8b7c890043a2f49e.png
[786945-20161206222444319-1066528329.jpg]: /images/20220315/a80b731bc2be4c16a8bbd108a5ba41a6.png
[786945-20161206222444679-518511660.png]: /images/20220315/1e43caf392924ede9bafa404948c2816.png
[786945-20161206222445132-1538640594.jpg]: /images/20220315/c76a16544e61413eb8f938f05e834f95.png