超有爱的分块技巧

分块思想，常用于处理区间问题，大概是把区间分为若干个块分别维护。

引子

通过之前讲的线段树和树状数组可以在 $O(n log n)$ 时间内解决本题, 但是这里有一个更好写的 $O(n \sqrt n)$ 做法.

考虑把区间分成长度为 $\sqrt n$ 的块

1. 区间加
   考虑如下一段区间：
   
   可以分成 $\le \Theta(\sqrt n)$ 块
   
   每一块都可以 O(1) 维护，所以总复杂都即为 $O(\sqrt n)$

2. 区间求和
   如上，还是把区间分成 $\le \Theta(\sqrt n)$ 块.

参考代码:

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL sum[N], add[N];
int n, m, len, w[N];
inline int get(int i)
{
    return i / len;
}
signed main(void)
{
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",w + i);
        sum[get(i)] += w[i];
    }
    
    for(int i = 1;i <= m;i++)
    {
        char op[3]; int l, r, d;
        scanf("%s %d %d\n", op, &l, &r);
        if(*op == 'Q')
        {
            LL ans = 0;
            if(get(l) == get(r))
            {
                for(int i = l;i <= r;i++) ans += w[i] + add[get(i)];
            }
            else
            {
                int i = l, j = r;
                while(get(i) == get(l)) ans += w[i] + add[get(i)], i++;
                while(get(j) == get(r)) ans += w[j] + add[get(j)], j--;
                for(int k = get(i); k <= get(j); k++) ans += sum[k];
            }
            printf("%lld\n", ans);
        }
        if(*op == 'C')
        {
            scanf("%d", &d);
            if(get(l) == get(r)) 
            {
                for(int i = l; i <= r; i++) w[i] += d, sum[get(i)] += d;
            }
            else
            {
                int i = l, j = r;
                while(get(i) == get(l)) w[i] += d, sum[get(i)] += d, i++;
                while(get(j) == get(r)) w[j] += d, sum[get(j)] += d, j--;
                for(int k = get(i); k <= get(j); k++) add[k] += d, sum[k] += d * len;
            }
        }
    }
}