时隔多月,终于对某些算法有了些了解.今天更一下树状数组.
之所以能用树状数组解决快速的区间查询和修改问题主要还是因为二进制的特点.
lowbit()函数很多博客都讲了,我也不说了.
C[1] = A[1]; C[2] = A[1] + A[2]; C[3] = A[3]; C[4] = A[1] + A[2] + A[3] + A[4]; C[5] = A[5]; C[6] = A[5] + A[6]; C[7] = A[7]; C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];
A是我们已知数组,我们不妨把C看成一个类前缀的形式.我们要查询一个区间[l,r]的和,我们可以用前缀的思想直接拿sum[r]-sum[l-1].至于sum数组怎么求呢,很容易发现每个C数组的区间长度都是lowbit(i),假设我们现在的位子是pos,那我们我们可以直接拿pos-lowbit(pos),然后+C[pos],然后循环这个过程就是sum[pos]了,可见复杂度最坏也就log(n),因为是按位处理的.
第二个是如何把这颗树建立起来,建树的复杂度也就log(n),对于我现在这个点,那些C可能包含我呢?可以给大家举个栗子来看一下,就拿二进制数是10110这个点来说吧,11000会包括它,为什么呢?一个数要包括另外一个数的先决条件是我这个数>=你这个数.
又因为lowbit的缘故,假定我当前这个数为4(100),那么包括4(100)的有哪些,101可以不?111可以不?可以证明都不可以,为什么呢,因为这些增加了x,但是lowbit(pos+x)>x,且可以证明当pos+lowbit(pos),我增加lowbit(pos),且我一定有lowbit(pos+lowbit(pos))>lowbit(pos).
我们可以证明x<lowbit(pos)一定不行,因为我这个数最多增加的区间是lowbit(x),因为前面全是0,而我加的数是x,而x>=lowbit(x)的,所以一定不行,如此就证明完成了.
好了.有了这些简单的单点修改和区间查询就可以解决了.
一共15个题CM的题单.(虽然不是dalao也是题单吧 https://www.luogu.com.cn/training/1143
第一题就算上面讲的这些...因为树状数组的讲解都没证明,我就证明了一下,有点小小的啰嗦了..P3374题目都是洛谷的.
//树状数组专项练习
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int sum[N],a[N];//一个建树存和,一个是原数组.
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void build(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int x)
{
int res=0;
while(x>0)
{
res+=sum[x];
x-=lowbit(x);
}
return res;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
build(i,a[i]);
}
while(m--)
{
int f;
scanf("%d",&f);
if(f==1)
{
int x,k;
scanf("%d%d",&x,&k);
build(x,k);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(y)-query(x-1));
}
}
return 0;
}
P3368这题是区间修改加单点查询,对于这个我们直接差分就行了,对于前面那个,我们存每个的差分的值,然后直接套用就ok了?
//树状数组专项练习
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int sum[N],a[N];//一个建树存和,一个是原数组.
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void build(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int x)
{
int res=0;
while(x>0)
{
res+=sum[x];
x-=lowbit(x);
}
return res;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
build(i,a[i]-a[i-1]);
}
while(m--)
{
int f;
scanf("%d",&f);
if(f==1)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
build(x,k);
build(y+1,-k);
}
else
{
int x,y;
scanf("%d",&x);
printf("%d\n",query(x));
}
}
return 0;
}
第三题P4939第二题随便改改就可以了..
//树状数组专项练习
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int sum[N],a[N];//一个建树存和,一个是原数组.
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void build(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int x)
{
int res=0;
while(x>0)
{
res+=sum[x];
x-=lowbit(x);
}
return res;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
while(m--)
{
int f;
scanf("%d",&f);
if(f==0)
{
int x,y,k=1;
scanf("%d%d",&x,&y);
build(x,k);
build(y+1,-k);
}
else
{
int x,y;
scanf("%d",&x);
printf("%d\n",query(x));
}
}
return 0;
}
第四题P5057 [CQOI2006]简单题也是在上面模板中加了两个字母,因为单个点的值是＝取反次数&1的.
//树状数组专项练习
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int sum[N],a[N];//一个建树存和,一个是原数组.
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void build(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int x)
{
int res=0;
while(x>0)
{
res+=sum[x];
x-=lowbit(x);
}
return res;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
while(m--)
{
int f;
scanf("%d",&f);
if(f==1)
{
int x,y,k=1;
scanf("%d%d",&x,&y);
build(x,k);
build(y+1,-k);
}
else
{
int x;
scanf("%d",&x);
printf("%d\n",query(x)&1);
}
}
return 0;
}第五题P2068 统计和(第一个讲解裸题,注意数据全部爆int)
//树状数组专项练习
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=1e5+5;
int sum[N],a[N];//一个建树存和,一个是原数组.
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void build(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int x)
{
int res=0;
while(x>0)
{
res+=sum[x];
x-=lowbit(x);
}
return res;
}
signed main()
{
int m;
scanf("%lld%lld",&n,&m);
while(m--)
{
char c;
cin>>c;
if(c=='x')
{
int x,y;
scanf("%lld%lld",&x,&y);
build(x,y);
}
else
{
int x,y;
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(y)-query(x-1));
}
}
return 0;
}
第六题:CF44C 也是区间修改单点查询按题意模拟即可.
//树状数组专项练习
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int sum[N];//一个建树存和,一个是原数组.
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void build(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int x)
{
int res=0;
while(x>0)
{
res+=sum[x];
x-=lowbit(x);
}
return res;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
build(x,1);
build(y+1,-1);
}
int f=1;
for(int i=1;i<=n;i++)
{
int x=query(i);
if(x!=1)
{
f=0;printf("%d %d\n",i,x);break;
}
}
if(f) puts("OK");
return 0;
}第七题:P2367(很简单的题,但是O2优化记得开一下...不知道是什么东西)
//树状数组专项练习
#include <bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int sum[N],a;//一个建树存和,一个是原数组.
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void build(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int x)
{
int res=0;
while(x>0)
{
res+=sum[x];
x-=lowbit(x);
}
return res;
}
int main()
{
int m,pre=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
build(i,a-pre);
pre=a;
}
while(m--)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
build(x,k);
build(y+1,-k);
}
int ans=2e9;
for(int i=1;i<=n;i++)
{
int x=query(i);
if(query(i)<ans) ans=query(i);
}
printf("%d\n",ans);
return 0;
}因为有比赛的原因,分为几段了Hhhh..
京公网安备 11010502036488号