题目描述
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 数列中第 l~r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
$1≤N,M≤10^{5}$
| d |≤$10^{4}$,
| A[i] |≤ $10^{9}$
样例
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例：
4
55
9
15
算法1
(分块) $O(n\sqrt{n})$
一段区间，分成若干小块，每块大小为$\sqrt{n}$。对于下标为 $ i $ 的数，它位于第 $[\frac{i}{\sqrt{n}}]$ 块。对于第 $i$ 块，其下标范围是$[i\sqrt{n},(i+1)\sqrt{n})$
主要思想：大块就打标记，小块就暴力循环
变量含义：B代表块的数量，base数组表示每一块额外加的数，res数组表示每一块的总和
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=100010;
int a[N],B,n,m;
LL res[N],base[N];
LL query(int l,int r){
int idl=l/B,idr=r/B;//先把块号求出
LL ans=0;
if(idl==idr){//如果位于同一块，就暴力
for(int i=l;i<=r;i++){
ans+=a[i]+base[idl];//原数+这一块被后来加的数，因为可能不是一整块，不能用res数组
}
return ans;
}else{
for(int i=l;i<(idl+1)*B;i++){//左边界
ans+=a[i]+base[idl];//原数+这一块被后来加的数，因为可能不是一整块，不能用res数组
}
for(int i=idl+1;i<idr;i++){//一整块一整块的加
ans+=res[i];//因为是整块，使用res数组
}
for(int i=idr*B;i<=r;i++){//右边界
ans+=a[i]+base[idr];//原数+这一块被后来加的数，因为可能不是一整块，不能用res数组
}
}
return ans;
}
void modify(int l,int r,int x){
int idl=l/B,idr=r/B;//先把块号求出
if(idl==idr){//如果位于同一块，就暴力
for(int i=l;i<=r;i++){
a[i]+=x;//原数修改
res[idl]+=x;//始终保持res数组含义的正确，即该块的总和
}
}else{
for(int i=l;i<(idl+1)*B;i++){//左边界
a[i]+=x;//原数修改
res[idl]+=x;//始终保持res数组含义的正确，即该块的总和
}
for(int i=idl+1;i<idr;i++){//一整块一整块的修改
base[i]+=x;//该整块有一个偏移量x
res[i]+=B*x;//始终保持res数组含义的正确，即该块的总和
}
for(int i=idr*B;i<=r;i++){//右边界
a[i]+=x;//原数修改
res[idr]+=x;//始终保持res数组含义的正确，即该块的总和
}
}
}
int main(){
scanf("%d%d",&n,&m);
B=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
res[i/B]+=a[i];
}
while(m--){
char op[2];
int l,r,x;
scanf("%s",op);
if(*op=='Q'){
scanf("%d%d",&l,&r);
printf("%lld\n",query(l,r));
}else{
scanf("%d%d%d",&l,&r,&x);
modify(l,r,x);
}
}
return 0;
}
算法2
(fhq-treap) $O(nlog(n))$
fhq-treap在本题中维护一个区间。
主要思想：将修改/查询的那一个区间分离出来，在这段区间修改/查询完毕后，再合并回去。
注意：在pushup时与线段树的不同，fhq-treap每个结点的sum/size除了要加上左右两个孩子以外，还要加上自己本身的sum/size
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=100010;
struct Node{
int l,r,val,size;
LL key,tag,sum;
}tr[N];
int root,idx;
LL getsum(int p){
return p?tr[p].sum+tr[p].size*tr[p].tag:0;
}
void pushup(int p){
if(!p)return ;
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
tr[p].sum=tr[p].key+tr[p].tag;//还要考虑tag
if(tr[p].l)tr[p].sum+=getsum(tr[p].l);
if(tr[p].r)tr[p].sum+=getsum(tr[p].r);
}
void pushdown(int p){
if(tr[p].tag){
tr[p].key+=tr[p].tag;
tr[p].sum+=tr[p].tag*tr[p].size;
if(tr[p].l)tr[tr[p].l].tag+=tr[p].tag;
if(tr[p].r)tr[tr[p].r].tag+=tr[p].tag;
tr[p].tag=0;
}
}
void split(int p,int &pl,int &pr,int x){
if(!p){
pl=pr=0;
}else{
pushdown(p);
if(tr[tr[p].l].size+1<=x){
pl=p;
split(tr[p].r,tr[pl].r,pr,x-tr[tr[p].l].size-1);
pushup(pl);
}else{
pr=p;
split(tr[p].l,pl,tr[pr].l,x);
pushup(pr);
}
}
}
void merge(int &p,int pl,int pr){
if(!pl||!pr){
p=pl?pl:pr;
return ;
}else{
pushdown(pl);
pushdown(pr);
if(tr[pl].val<tr[pr].val){
p=pl;
merge(tr[p].r,tr[pl].r,pr);
}else{
p=pr;
merge(tr[p].l,pl,tr[pr].l);
}
pushup(p);
}
}
int newNode(LL key){
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].tag=0;
tr[idx].sum=key;
tr[idx].size=1;
return idx;
}
void insert(int &p,int id,int x){
int p1=0,p2=0;
split(p,p1,p2,id-1);
merge(p,p1,newNode(x));
merge(p,p,p2);
}
void add(int &p,int l,int r,int dx){
int p1=0,p2=0,p3=0,p4=0;
split(p,p1,p2,l-1); //分离
split(p2,p3,p4,r-l+1);
tr[p3].tag+=dx; //修改
merge(p2,p3,p4); //合并
merge(p,p1,p2);
}
LL query(int &p,int l,int r){
int p1=0,p2=0,p3=0,p4=0;
split(p,p1,p2,l-1); //分离
split(p2,p3,p4,r-l+1);
LL ans=tr[p3].sum; //查询
merge(p2,p3,p4); //合并
merge(p,p1,p2);
return ans;
}
void in_order(int p){//中序遍历可以实时输出修改后的数组
pushdown(p);
if(tr[p].l)in_order(tr[p].l);
printf("%lld ",tr[p].key);
if(tr[p].r)in_order(tr[p].r);
}
int main(int argc, const char * argv[]) {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
insert(root,i,x);
}
char op[2];
int l,r;
LL dx;
for(int i=1;i<=m;i++){
scanf("%s%d%d",op,&l,&r);
if(*op=='Q'){
printf("%lld\n",query(root,l,r));
}else if(*op=='C'){
scanf("%lld",&dx);
add(root,l,r,dx);
// in_order(root);
// cout<<endl;
}
}
return 0;
}
算法3
(线段树) $O(nlog(n))$
常规做法
参考文献
https://www.acwing.com/activity/content/code/content/167900/
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int w[N],n,m;
typedef long long LL;
struct Node{
int l,r;
LL sum,add;
}tr[4*N];
void pushup(int u){
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(root.add){
left.add+=root.add;
right.add+=root.add;
left.sum+=(LL)(left.r-left.l+1)*root.add;
right.sum+=(LL)(right.r-right.l+1)*root.add;
root.add=0;
}
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,w[l],0};
}else{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int d){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].add+=d;
tr[u].sum+=(tr[u].r-tr[u].l+1)*d;
}else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)modify(u<<1,l,r,d);
if(r>mid)modify(u<<1|1,l,r,d);
pushup(u);
}
}
LL query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].sum;
}else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
LL res=0;
if(l<=mid)res=query(u<<1,l,r);
if(r>mid)res+=query(u<<1|1,l,r);
return res;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
build(1,1,n);
char op[2];
int l,r,x;
while(m--){
scanf("%s",op);
if(*op=='Q'){
scanf("%d%d",&l,&r);
printf("%lld\n",query(1,l,r));
}else{
scanf("%d%d%d",&l,&r,&x);
modify(1,l,r,x);
}
}
return 0;
}
算法4
(树状数组) $O(nlog(n))$
维护两个前缀和
参考文献
https://www.acwing.com/activity/content/code/content/164758/
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
int a[N],n,m;
LL tr1[N],tr2[N];
int lowbit(int x){
return x&-x;
}
void add(LL tr[],int x,LL c){
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}
LL sum(LL tr[],int x){
LL res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
LL pre(int x){
return sum(tr1,x)*(x+1)-sum(tr2,x);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for (int i = 1; i <= n; i ++ )
{
int b = a[i] -a[i-1];
add(tr1,i,b);
add(tr2,i,(LL)b*i);
}
while(m--){
char op[2];
int l,r,d;
scanf("%s%d%d",op,&l,&r);
if(*op=='C'){
scanf("%d",&d);
add(tr1,l,d), add(tr2,l,l*d);
add(tr1,r+1,-d), add(tr2,r+1,(r+1)*-d);
}else{
printf("%lld\n",pre(r)-pre(l-1));
}
}
return 0;
}
