题目描述

给定一个长度为 N 的数列 A，以及 M条指令，每条指令可能是以下两种之一：

C l r d，表示把 A[l],A[l+1],…,A[r]都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。

对于每个询问，输出一个整数表示答案。

题目链接：
https://www.acwing.com/problem/content/description/244/

样例

略

算法1

由于涉及大量计算块位置的运算，故把计算块运算改为位运算，即块的大小改为小于且最大的2幂次（小于n的根号）
时间一下降了一半。从1100ms降为410ms.

C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=100010, M=1350;

int w[N],n,m,k2;
LL add[M], sum[M];

void change(int l, int r, int d){
    if( (l>>k2)==(r>>k2) )
        for(int i=l;i<=r;i++) w[i]+=d, sum[i>>k2]+=d;
    else {
        int i=l, j=r;
        while( (i>>k2)==(l>>k2) ) w[i]+=d, sum[i>>k2]+=d, i++;
        while( (j>>k2)==(r>>k2) ) w[j]+=d, sum[j>>k2]+=d, j--;
        for(int k=(i>>k2);k<=(j>>k2);k++) sum[k]+=d<<k2, add[k]+=d;
    }
}

LL query(int l, int r){
    LL res=0;
    if( (l>>k2)==(r>>k2) )
        for(int i=l; i<=r; i++) res+=w[i]+add[i>>k2];
    else {
        int i=l, j=r;
        while( (i>>k2)==(l>>k2) ) res+=w[i]+add[i>>k2], i++;
        while( (j>>k2)==(r>>k2) ) res+=w[j]+add[j>>k2], j--;
        for(int k=(i>>k2);k<=(j>>k2);k++) res+=sum[k];
    }
    return res;
}

int main(){
    cin>>n>>m;
    for(int i=1,j=0;i*i<n;i*=2,j++) k2=j;
    for(int i=1;i<=n;i++)
        scanf("%d", &w[i]), sum[i>>k2]+=w[i];

    char op[2];
    int l,r,d;
    while(m--){
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='C'){
            scanf("%d",&d);
            change(l,r,d);
        } else 
            printf("%lld\n",query(l,r));
    }
}