树状数组【学习B站视频笔记】

树状数组

1、树状数组是什么

    树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和。但是每次只能修改一个元素的值。

2、树状数组干什么用的

      最简单的树状数组就是用来解决动态前缀和问题的数据结构。这个数组是动态的，也就是说这些值在某些时候会发生变化。

3、树状数组具体图解

     

令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：

C1 = A1

C2 = A1 + A2

C3 = A3

C4 = A1 + A2 + A3 + A4

C5 = A5

C6 = A5 + A6

C7 = A7

C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

...

C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16

这里有一个有趣的性质：

设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，

所以很明显：Cn = A(n – 2^k + 1) + ... + An

举例：

13=1101=A[13]；

往前找：12=1100=A[9]+A[10]+A[11]+A[12];

继续往前找 8=1000=A[1]+..A[8];

可以看出是逐渐消1致0得出的结果。

可以用Lowbit：x&(-x)实现。

同时从这里的树也可以分析出来：对一个值的改变能够影响的总体是沿着树往上走的，

每一次都向非0位过后的第一个最小的0变为1上升：10001100=>10011100.

目前不知道具体这个上升这么操作的原因是什么。//PS：有大神知道能否告诉我一下 靴靴。

 

HDU 1166

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set> 
using namespace std; 

int sum[200050];
int n;
int lowbit(int x)
{
	return x&(-x);
} //返回最小的值

void update(int pos,int val)//单点修改 
{
	while(pos<=n)
	{
		sum[pos]+=val;
		pos+=lowbit(pos);
	}
}//维护的是前缀和 

int query(int pos)
{
	if(pos==0)return 0;
	int s=0;
	while(pos)
	{
		s+=sum[pos];
		pos-=lowbit(pos);
	}
	return s;	
}//就算是前面的更新,也只是把需要用到的更新了，求区间和的时候需要按1的位置加起来。 

int main()
{
    string s;
    int T;
    cin>>T;
    int i,j;
	int cnt=0,pre;
	while(T--)
    {
    	cin>>n; 
    	printf("Case %d:\n",++cnt);
    	memset(sum,0,sizeof(sum));
		for(int k=1;k<=n;k++)
    	{
	    	scanf("%d",&pre);
	    	update(k,pre);
	    }
	    cin>>s;
	    while(s[0]!='E') 
	    {
	    	if(s[0]=='A')
	    	{
	    		cin>>i>>j;
	    		update(i,j);
	    	}
	    	if(s[0]=='S')
	    	{
	    		cin>>i>>j;
	    		update(i,-j);
	    	}
	    	if(s[0]=='Q')
	    	{
	    		cin>>i>>j;
	    		cout<<query(j)-query(i-1)<<endl;
	    	}
    		cin>>s;
    	}
    	
    }
}