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

树状数组

程序员文章站 2022-03-21 21:22:49
...

树状数组,顾名思义,树状的数组,其目的是优化区间查询和区间修改的复杂度。

看图

       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

树状数组

 

以9为例,C[9]=A[9]+C[8]即可;

而其中的k用了一个巧妙的方式,lowbit()

int lowbit(int x){

  return x&(x^(x–1));

  }

如:

x =1: 1 &-1(设位数为8)0000 0001 & 1111 1111 = 1

x = 6:6 & -6 0000 0110 &1111 1010 = 2 //补码&运算

总结一下,其实就是:

求出2^p(其中p: x 的二进制表示数中, 右向左数第一个1的位置),如6的二进制表示为110,向左数第零个为0,第一个为1,则p=1,故Lowbit(6) = 2^1 = 2。

其中最不好理解的就是数组的更新初始化(困扰快两天了,,,)当时一直不明白A[]数组如何储存的,如何转化成C[]数组的,其实根本不用储存A[]数组

用的是他的修改功能

void add(int x,int value)
{
         while(x<Max)
         {
                  c[x]+=val;
                  x+=lowbit;
         }
}

其中value就是对应的A[]数组

举个例子,数组1~10;如何将其储存在C数组中呢,只需要将1~10赋值给value即可

那么如何求和呢,下面是树状数组的第二个功能代码

 

int getsum(int k)
{
	int sum=0;
	while(k>0){
		sum+=d[k];
		k-=lowbit(k);
	}
	return sum;
}

这个就非常好理解啦!如果我想求1~10的和,只需传入10既可以啦~

那么如果我想求的区间不是从1开始呢

也非常简单,例如我要求区间[r,l]的区间和,那么就是getsum(l)-getsum(r-1);这里r一定要减一,不然就不包含r本身了。

其实就是那么简单啦,完整代码如下(例求1~10)的和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
int d[32005],l[32005];
int lowbit(int k)
{
	return (k&(-k));
}
void add(int pos,int v)
{
	while (pos <= 100 + 1)
	{
		d[pos]+=v;
		pos += lowbit(pos);
	}
}
int getsum(int k)
{
	int sum=0;
	while(k>0){
		sum+=d[k];
		k-=lowbit(k);
	}
	return sum;
}
int main(){
	
	memset(d,0,sizeof(d));
	for(int i=1;i<=100;i++)
	{
		int t;
		t=i;
		add(i,t);
	}
	cout<<getsum(10)<<endl;
	return 0;
	
}

 

相关标签: 树状数组