相信大家刚接触c++学数组的时候,肯定听过这一段话
数组,它就像一列长长的火车,每个火车厢里装着一位乘客......
但我相信,有一种数据结构,能让开心的OIer瞬间泪流满面,能让程序员抓耳挠腮,能让初学者老做噩梦…
路人甲:好可怕的数据结构,我要回家找妈妈...(逃)
它就是Oler一大头疼点:树!
如果我说数组跟树是一个玩意儿,你信吗
路人乙:不信,数组那么单纯可爱,伴随着我走过那么多个春秋,我绝不允许你把我最爱的数组和我最讨厌的树相提并论!
咳咳,好吧,估计真的要颠覆你的认知了,因为,今天的数组,就是长得跟树一样!
它就是我们的————树状数组!
一,树状数组长啥样
我能说我bzd吗
某OIer:它有蓝蓝的大眼睛,乌黑的长头发,曼妙的身姿...
作者:我叫你把树状数组长啥样告诉我,你咋把你梦中情人说出来了?
某OIer:你懂树状数组吗?你压根就...
作者:[○・`Д´・ ○]
某OIer:你压根就很懂啊,我把你画的图给你
注:正方形表示我们原来的A数组,圆形表示我们的树状数组C
这玩意儿咋用呢?
举个例子,我们要求4的前缀和,那么就是C4,如果要求5的前缀和那么就是C4+C5
二,树状数组构建
一个人放梯子,然后使用了这个梯子的人就要连接它,如果无法爬上梯子(例如有高度为2的梯子但没有高度为1的梯子),那么就自己放一个宽度为1,高度为1的梯子。
每个点宽度与高度相等,节点k放置的梯子只用k+1和k+宽度k的节点才能使用
放图示
C1为了方便后面的节点跳上高度2,放置了一个高度为1,宽度为1的梯子
C2跳上了C1的梯子,来到了高度2,由于使用了C1的梯子,所以要和C1连接,并搭建一个高度为2,宽度为2的梯子
由于C1宽度不够,C3无法跳上C2的梯子,只能自己放置一个宽度和高度均为1的梯子
C4跳上C3的梯子,来到高度2,又跳上C2的梯子,来到高度4,并连接C3和C2,然后建起一个高度和宽度为4的桥,方便下一个点跳上高度为8的位置
三,利用lowbit快速求2^k
lowbit(int x)=x & -x
(k为从右往左数时,数到1停止,当前数了多少个0)
没错,就是这么简单。
先来扩展一下:负数的二进制为其绝对值二进制的反码加1
先举个例子:x=11
x的二进制: 1011
-x的二进制:0101
x&-x: 0001
转化成十进制是1,2^0=1
不信?再来一个!x=58
x的二进制: 111010
-x的二进制:000110
x&-x: 000010
转化成二进制是2,2^1等于2
lowbit就介绍到这里,下面讲讲单点更新
四:单点更新
先把图放上
节点右边的4位二进制是索引
问:修改C5对其他节点的影响
C5的父节点依次是C6和C8,对它们两个节点产生了影响
神奇的事发生了:
C(5+lowbit(5))=C(5+1)=C(6)
C(6+lowbit(6))=C(6+2)=C(8)
现在lowbit函数的作用大家都清楚了:
father(i)=i+lowbit(i)
如此一来,单点更新的代码也呼之欲出了
int lowbit(int x){return x&-x;}
void add(int index,int value)//单点增加(index为下标,value为数值)
{
while(index<=n)
{
a[index]+=value;
index+=lowbit(index);
}
}
五:前缀和
(还是第四节那张图,不放了)
举个例子,我们要求前缀和6
那么前缀和6=C(6)+C(4),而恰好,C(4)=C(6-lowbit(6))
再举个例子把,我们要求前缀和7
前缀和7=C(7)+C(6)+C(4),当然,C(6)=C(7-lowbit(7)),C(4)=C(6-lowbit(6))
根据前面的例子,求前缀和的代码也出来了
long long sum(int index)//前缀和(index为下标)
{
long long ans=0;
while(index>0)
{
ans+=a[index];
index-=lowbit(index);
}
return ans;
}
六,树状数组,不仅于此
虽然前面说了一大通骂树的话,但树也是有很大的包容性的。
就拿我们今天的树状数组来说,只需要稍加改动就可以变成二维,甚至多加一个,就可以做到区间内的更新与查询。
再提提昨天讲的树上倍增,我例子代码用的是求最大值,完全可以改成求最小值,求和,求最大公约数…
(树上倍增有兴趣的点这)
这里给出二维树状数组以及区间更新区间查询和的代码,可自行研究
int a[1030][1030],n;
int lowbit(int x){return x&-x;}
void add(int x,int y,int value)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
a[i][j]+=value;
}
long long sum(int x,int y)
{
long long ans=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans+=a[i][j];
return ans;
}
//二维树状数组
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
struct Tree
{
ll a[maxn];
void add(int x,ll d)
{
for(;x<maxn;x+=x&-x)
a[x]+=d;
}
ll Sum(int x)
{
ll ans=0;
for(;x>0;x-=x&-x)
ans+=a[x];
return ans;
}
}D,Dn;
int n,m,x,y,a,t;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&t,&x,&y);
if(t==1)
{
scanf("%d",&a);
D.add(x,a);D.add(y+1,-a);
Dn.add(x,(ll)a*x);
Dn.add(y+1,-(ll)a*(y+1));
}
else
{
ll ans=0;
ans+=D.Sum(y)*(y+1)-Dn.Sum(y);
ans-=D.Sum(x-1)*x-Dn.Sum(x-1);
printf("%lld\n",ans);
}
}
return 0;
}
//区间增加,区间查询和(t==1的为增加,else的为求和)
七,后记
最近阅读量和赞都好少,能点个赞吗?你们的赞是我更新的最大动力。
%%%