欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-21 19:33:36
...

树状数组

1、树状数组是什么

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

2、树状数组干什么用的

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

3、树状数组具体图解

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

令这棵树的结点编号为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:有大神知道能否告诉我一下 靴靴。

 

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

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;
    	}
    	
    }
}

 

相关标签: 树状数组