一个简单的整数问题2

解题思路

本题需要实现两个操作，一个是区间加上一个数，一个是查询区间和。每次的操作如果暴力的去操作需要 $O(n)$ 的时间复杂度，一共 $m$ 个操作，总共的时间复杂度就是 $O(nm)$，一定会超时。

而本题不管用树状数组还是线段树都可以将单次操作的时间复杂度降为 $O(logn)$，这样整个的时间复杂度就不会超时。这里不用这两种方法，我们用分块也可以解决本题。

我们如果暴力的话，那么每次都需要遍历区间中的每一个数，这样每次操作的时间复杂度就很慢，而分块就是一个相对于线段树和树状数组来说要更朴素的一个做法。

分块的思想本质上也是一个暴力的做法，就是将原数组分成若干段，一般来说是分成 $\sqrt{n}$ 段，这样每一段的长度以及段数都是 $\sqrt{n}$

假设我们现在要将 $l \sim r$ 中每个数加上 $d$，此时 $l \sim r$ 会被分成若干段，中间的若干段都是完整的段，而左、右两端则是不完整的段。而中间完整段的数量一定不超过 $\sqrt{n}$，左、右两端又都是不完整的段，因此这两部分的长度也都不超过 $\sqrt{n}$，这样我们就能将任何一次查询的区间分割成不超过 $\sqrt{n}$ 个完整段，和两个长度不超过 $\sqrt{n}$ 的段。

这样我们可以用某张方式来将不超过 $\sqrt{n}$ 个完整段统一处理，将两个长度不超过 $\sqrt{n}$ 的不完整段通过枚举来处理。这样就能将每次操作的时间复杂度降为 $O\sqrt{n}$，这样整个的时间复杂度就不会超时了。

首先我们按照分块的思想将整个区间分成 $\sqrt{n}$ 段，然后考虑一下每一段分别需要记录哪些信息，首先我们会给很长的一段完整区间加上一个数，为了能提高效率，我们可以利用懒标记的思想。

对于修改操作来说，我们要给 $l \sim r$ 一整段每个数都加上 $d$，中间的完整段中每一段的每一个位置都要加上一个 $d$，我们就可以给每一段记录一个懒标记 $add$，表示本段里的所有数都要加上一个 $add$。而对于每个完整段，我们希望能快速知道本段的总和，因此我们可以用一个 $sum$ 表示本段的真实数值和（算上 $add$）。

确定了每一段需要维护的信息之后，我们就可以考虑如果执行两种操作，对于修改操作，首先将要修改的区间分成若干个完整段和左、右两个不完整段。对于每个完整段，要将段内的每个数都加上 $d$，因此我们令每个完整段对应的 $add$ 加上 $d$，$sum$ 加上 $d \times length$，$length$ 表示该段的长度。对于左、右两个不完整段，我们直接暴力枚举不完整段中的所有数，对于每个数，都要加上 $d$，同理要更新该段的 $sum = sum + d$。

对于查询操作，我们也将要查询的区间分成若干个完整段和左、右两个不完整段，对于每个完整段，我们直接累加 $sum$ 即可，而对于左、右两个不完整段，直接暴力枚举段内的所有数进行求和即可。最终得到的就是整个查询区间的和

可以发现以上两个操作都分为完整段和不完整段来处理，完整段统一进行处理，不完整段暴力枚举处理，由于完整段的数量不超过 $\sqrt{n}$，而不完整段内部所有数的数量也不超过 $\sqrt{n}$，因此每次操作的时间复杂度都在 $O(\sqrt{n})$，因此 $m$ 个操作的时间复杂度就是 $O(m\sqrt{n})$，不会超时。

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 100010, M = 350;

int n, m, len;
int a[N];
//add[i] 表示第 i 段中每个数需要加上的值，sum[i] 表示第 i 段的真实数值和（算上 add）
LL add[M], sum[M];

int get(int i) //返回下标 i 在第几段
{
    //(i - 1) / len 表示 1 ~ len 为第 0 段，len + 1 ~ 2 * len 为第 1 段
    //i / len 表示 i ~ len - 1 为第 0 段，len ~ 2 * len - 1 为第 1 段
    return (i - 1) / len;
}

void modify(int l, int r, int d) //将 l ~ r 中的每个数加上 d
{
    if(get(l) == get(r)) //如果 l 和 r 在同一段内，直接暴力
    {
        for(int i = l; i <= r; i++) a[i] += d, sum[get(i)] += d;
    }
    else
    {
        //到这说明 l 和 r 不在同一段内，分两部分处理
        int i = l, j = r;
        while(get(i) == get(l))  a[i] += d, sum[get(i)] += d, i++; //暴力处理左边不完整段
        while(get(j) == get(r))  a[j] += d, sum[get(j)] += d, j--; //暴力处理右边不完整段
        for(int k = get(i); k <= get(j); k++) add[k] += d, sum[k] += len * d; //统一处理中间完整段
    }
}

LL query(int l, int r) //查询 l ~ r 中的所有数的和
{
    LL res = 0; //记录答案
    if(get(l) == get(r)) //如果 l 和 r 在同一段内，直接暴力
    {
        for(int i = l; i <= r; i++) res += a[i] + add[get(i)];
    }
    else
    {
        //到这说明 l 和 r 不在同一段内，分成两部分处理
        int i = l, j = r;
        while(get(i) == get(l)) res += a[i] + add[get(i)], i++; //暴力处理左边不完整段
        while(get(j) == get(r)) res += a[j] + add[get(j)], j--; //暴力处理右边不完整段
        for(int k = get(i); k <= get(j); k++) res += sum[k]; //统一处理中间完整段
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    len = sqrt(n); //表示每一段的长度
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum[get(i)] += a[i]; //初始化每一段的最开始的数值和
    }

    char op[2];
    int l, r, d;
    while(m--)
    {
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'C')
        {
            scanf("%d", &d);
            modify(l, r, d); //修改操作
        }
        else printf("%lld\n", query(l, r)); //查询操作
    }
    return 0;
}