树状数组浅谈-爱代码爱编程
在进行数组处理时可能会遇到以下需求:单点更改某位置的值;查询某个区间[left, right]内的值的和,如果普通地进行遍历数组,则时间复杂度可能达到O(n^2),为了降低时间复杂度,可以使用树状数组来实现单点修改和区间求和。
lowbit()函数原理及作用
在正式学习树状数组之前,需要介绍一下lowbit()函数。
lowbit函数的写法如上,他的作用是得到非负整数 i 在二进制表示下,最低位的 1 与其后面的所有 0 组成的数值。
e.g. lowbit(8)=lowbit(100)(100是二进制表示下的8)= 8;
lowbit (9)=lowbit (101) (101是二进制表示下的9)=1;
lowbit(44)=lowbit(101100)(101100是二进制表示下的44)=8;
而这一操作实际上可以通过以下方式得到:对原数字取反加一。以 i=44 为例,对101100取反得到010011,加一得到010100.这时我们发现,蓝色数字和紫色数字如果按位与,则得到的数是00100,正是lowbit(44)的结果。我们又知道,计算机存储的数是补码形式,而 ~i+1= -i(~是取反符号,这个式子意为: -i 就是对 i 进行取反加一操作),并且一个数取反加一两次后得到的仍是原数,所以lowbit(i)=(-i)& i 。
那么为什么要引入lowbit函数呢?观察一下
(图源树状数组,就是这么简单!_哔哩哔哩_bilibili)
这种图片里的c [ ]数组(实际上就是树状数组),将每个数组里的数字以二进制数表示,类似下图。
(图源树状数组,就是这么简单!_哔哩哔哩_bilibili)
可以看到,对树状数组里的序号数取lowbit值后得到的就是该数组元素里存放的数据个数。例如: t [1]里有一个数据,lowbit(1)==1.t [2]里有2个数据,lowbit(2)==2.t [3]里有1个数据,lowbit(3)==1……因此lowbit函数可以计算树状数组中某个元素包含几个数据。
应用:
c [6]的直接前驱是c [4],可以表示为c [ 6 - lowbit(6) ],c [6]的直接后继是c [8],可以表示为c [6 + lowbit(6) ],通过这种计算方法,可以便捷地实现单点修改和区间求和功能。
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10005;
int n,a[maxn],c[maxn];
int lowbit(int i){//c[i]的区间长度
return (-i)&i;
}
void add(int i,int z)//点更新,a[i]加上z
{
/*while(i+lowbit(i)<=n)
{
c[i]+=z;
i+=lowbit(i);
}*/
for(;i<=n;i+=lowbit(i))
c[i]+=z;
}
int sum(int i)//前缀和,a[1]+a[2]+...+a[i]
{
int sum=0;
for(;i>0;i-=lowbit(i))
sum+=c[i];
return sum;
}
int sum(int i,int j)//区间和,a[i]+a[i+1]+...+a[j]
{
/*int sum=0;
for(;j>=i;j-=lowbit(j))
sum+=c[j];
return sum;*/
return sum(j)-sum(i-1);
}
需要注意的是,单点修改时,不仅需要修改指定的点,还需要将该点的所有后继都进行修改,代码见上面的 add()函数。