题目描述
给定一个序列,维护“区间修改”和“区间求和”两种操作
【进阶课】分块
首先考虑暴力的做法
做任何区间操作都是一个O(n)的循环
$O(n^2)$的时间复杂度明显会超时
优化思路:将数列分成$\sqrt{n}$个长度为$\sqrt{n}$的块
区间中的整块一起处理,然后再处理两侧块内的部分
这样的话每次两侧块内最多跑$2\sqrt{n}$个数,中间最多跑$\sqrt{n}$个块,时间复杂度是$O(\sqrt{n})$的
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=100010,M=350;
int len;
LL add[M],sum[M];
int w[N];
inline int get(int x){ //获得x所在的块
return x/len;
}
inline void change(int l,int r,int d){ //区间修改
if(get(l)==get(r)){ //l和r在同一块内
for(int i=l;i<=r;i++)
w[i]+=d,sum[get(l)]+=d;
return;
}
int i=l,j=r;
while(get(i)==get(l)) //左侧块内
w[i]+=d,sum[get(l)]+=d,i++;
while(get(j)==get(r)) //右侧块内
w[j]+=d,sum[get(r)]+=d,j--;
for(int k=get(i);k<=get(j);k++) //中间跨块
sum[k]+=d*len,add[k]+=d;
}
inline LL query(int l,int r){ //区间求和
LL res=0;
if(get(l)==get(r)){
for(int i=l;i<=r;i++)
res+=w[i]+add[get(l)];
return res;
}
int i=l,j=r;
while(get(i)==get(l))
res+=w[i]+add[get(l)],i++;
while(get(j)==get(r))
res+=w[j]+add[get(r)],j--;
for(int k=get(i);k<=get(j);k++)
res+=sum[k];
return res;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
len=sqrt(n); //块的长度
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
sum[get(i)]+=w[i];
}
char type[2];
int l,r,d;
while(m--){
scanf("%s%d%d",type,&l,&r);
if(type[0]=='C'){
scanf("%d",&d);
change(l,r,d);
}
else
printf("%lld\n",query(l,r));
}
return 0;
}
【提高课】树状数组
lowbit(i):i的二进制表示中最后一个“1”代表的数(有点绕)
比如24的二进制表示是11000,最后一个1在1000这个位置,代表8,所以lowbit(24)=8
计算公式:lowbit(i)=i&-i
具体原因是:计算机采用补码,负数的二进制表示是按位取反再加1,所以i&-i能得到lowbit(i)
建立一个数组,第i位代表从i开始往前lowbit(i)个数的和
可以在O(logn)的时间复杂度内实现单点修改和查询前缀和
void add(int x){
for(;x<=n;x+=lowbit(x))
c[x]++;
}
int search(int x){
int res=0;
for(;x;x-=lowbit(x))
res+=c[x];
return res;
}
将A(原数组)做一次差分并求出树状数组c1,实现区间修改和单点查询
可以进一步总结规律实现由c1直接算出A的前缀和
A的差分数组:1 1 1 1 1 1 1 1 1 1
A的前缀和:1 3 6 10 15 21 28 36 45 55
以计算1+2+3+4=10为例,差分数组的前缀和(原数组)中
1=1,2=1+1,3=1+1+1,4=1+1+1+1
累加起来后第一个“1”加了4次,第二个“1”加了3次,以此类推
算前x个数的和时,差分后的第i(0<i<=x)个数加了x-i+1次
再定义一个数组B,B[i]=(A[i]-A[i-1])*i,c2为B的树状数组
求前缀和时返回c1[i]*(x+1)-c2[i]
神奇的事情出现了:
c1[i]*(x+1)中i往前lowbit(i)个数都被加了x+1次,
c2[i]中i往前lowbit(i)个数分别被加了下标次,
下标为j的数正好会被加x-j+1次
void add(int x,LL k){ //差分数组单点修改
for(int i=x;i<=n;i+=lowbit(i)){
c1[i]+=k;
c2[i]+=k*x;
}
}
LL search(int x){ //求1~x的前缀和
LL res=0;
for(int i=x;i;i-=lowbit(i))
res+=c1[i]*(x+1)-c2[i];
return res;
}
这样就在O(logn)的时间复杂度内实现了区间修改和查询前缀和
#include<iostream>
using namespace std;
const int N=100005;
typedef long long LL;
int n,m;
LL c1[N],c2[N];
int lowbit(int x){
return x&-x;
}
void add(int x,LL k){
for(int i=x;i<=n;i+=lowbit(i)){
c1[i]+=k;
c2[i]+=k*x;
}
}
LL search(int x){
LL res=0;
for(int i=x;i;i-=lowbit(i))
res+=c1[i]*(x+1)-c2[i];
return res;
}
int main(){
scanf("%d%d",&n,&m);
int last=0,now;
for(int i=1;i<=n;i++){
scanf("%d",&now);
add(i,now-last); //差分
last=now;
}
while(m--){
char type;
int x,y,k;
scanf("%s%d%d",&type,&x,&y);
if(type=='C'){
scanf("%d",&k);
add(x,k),add(y+1,-k); //区间修改
}
else
printf("%lld\n",search(y)-search(x-1)); //区间查询
}
return 0;
}
【提高课】线段树
建一颗二叉树,根节点代表整个区间,下面的两个儿子把区间劈成两半,直到不能劈为止
进行区间操作时如果当前节点包含在区间内就直接更新,否则递归到子节点
区间修改需要用到懒标记,就是这段区间要加几先记录下来,要用到区间内部的信息时再下推到子节点
带懒标记的线段树可以在O(logn)的时间复杂度内完成各种区间操作
#include<iostream>
using namespace std;
typedef long long LL;
struct node{
int l,r; //区间左右端点
LL sum,add; //区间和、懒标记
}tr[400005]; //空间要开到N的4倍
int a[100005];
void pushup(int x){ //维护区间和
tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
}
void pushdown(int x){ //下推懒标记
node &l=tr[x<<1],&r=tr[x<<1|1];
if(tr[x].add){
l.sum+=tr[x].add*(l.r-l.l+1);
l.add+=tr[x].add;
r.sum+=tr[x].add*(r.r-r.l+1);
r.add+=tr[x].add;
tr[x].add=0;
}
}
void build(int l,int r,int x){ //建树
if(l==r){
tr[x]={l,r,a[l]};
return;
}
tr[x]={l,r};
int mid=l+r>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
pushup(x);
}
void change(int l,int r,int d,int x){ //区间修改
if(tr[x].l>=l&&tr[x].r<=r){
tr[x].sum+=d*(tr[x].r-tr[x].l+1);
tr[x].add+=d;
return;
}
pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
if(l<=mid)
change(l,r,d,x<<1);
if(r>mid)
change(l,r,d,x<<1|1);
pushup(x);
}
LL search(int l,int r,int x){ //区间求和
if(tr[x].l>=l&&tr[x].r<=r)
return tr[x].sum;
pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
LL res=0;
if(l<=mid)
res+=search(l,r,x<<1);
if(r>mid)
res+=search(l,r,x<<1|1);
return res;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
while(m--){
char type[2];
int l,r,d;
scanf("%s%d%d",type,&l,&r);
if(type[0]=='C'){
scanf("%d",&d);
change(l,r,d,1);
}
else
printf("%lld\n",search(l,r,1));
}
return 0;
}
总结
个人认为分块比较好想,也能维护比较多的信息
线段树思路还是很清晰的,但代码长,难调,而且空间复杂度相当高
树状数组思路最复杂,能维护的信息较少,但写起来比较容易
线段树是最简单的,写这个题都不用改模板