P3372 分塊過線段樹模闆

分塊

算法參考

預處理時不要忘記ed[sq] = n

// Decline is inevitable,
// Romance will last forever.
#include <bits/stdc++.h>
using namespace std;
#define mst(a, x) memset(a, x, sizeof(a))
#define int long long
const int maxn = 1e5 + 10;
const int maxm = 2e4;
const int P = 1e9 + 7;
int n, sq;
int start[maxn], ed[maxn];  //start[i]表示第i個數所在的塊的最左側的點，ed表示最右側的點
int size[maxm], bel[maxn];  //size[i]表示第i塊的大小   bel[i]表示第i個數所在的塊是第幾塊
int a[maxn], sum[maxm], m;  //a[] 原始數組 sum[i] 第i塊的和 維護第i塊的資訊
int mark[maxm];             //mark[i]表示第i塊的每個數的值變化 類似delta偏移量
void init(int n) {
    sq = sqrt(n);           //每根号n個數一塊，一共sq塊
    for(int i = 1; i <= sq; i++) {  //求出每塊最左和最右側的點
        start[i] = n/sq * (i-1) + 1;
        ed[i] = n/sq * i;
    }
    ed[sq] = n;             //不要忘記！
    for(int i = 1; i <= sq; i++)
        for(int j = start[i]; j <= ed[i]; j++) {
            bel[j] = i;     //
        }
    for(int i = 1; i <= sq; i++)
        size[i] = ed[i] - start[i] + 1;
}
void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    init(n);
    for(int i = 1; i <= sq; i++)
        for(int j = start[i]; j <= ed[i]; j++)
            sum[i] += a[j];
    while(m--) {
        int d;
        cin >> d;
        if(d == 1) {
            int x, y, k;
            cin >>x >> y >> k;
            if(bel[x] == bel[y])
                for(int i = x; i <= y; i++) {
                    a[i] += k;
                    sum[bel[i]] +=k;
                }
            else {
                for(int i = x; i <= ed[bel[x]]; i++) {
                    a[i] += k;
                    sum[bel[i]] += k;
                }
                for(int i = start[bel[y]]; i <= y; i++) {
                    a[i] += k;
                    sum[bel[i]] += k;
                }
                for(int i = bel[x]+1; i < bel[y]; i++) {
                    mark[i] += k;      //對區間的每個數都加k，mark[i]表示第i塊的所有數都+k
                }
            }
        }
        else {
            int x, y;
            cin >> x >> y;
            if(bel[x] == bel[y]) {
                int ans = 0;
                for(int i = x; i <= y; i++)
                    ans += a[i];
                cout << ans << endl;
            }
            else {
                int ans = 0;
                for(int i = x; i <= ed[bel[x]]; i++)
                    ans += a[i] + mark[bel[i]];
                for(int i = start[bel[y]]; i <= y; i++)
                    ans += a[i] + mark[bel[i]];
                for(int i = bel[x] + 1; i < bel[y]; i++)
                    ans += sum[i] + size[i] * mark[i];
                cout << ans << endl;
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int T; scanf("%d", &T); while(T--)
//    int T; cin >> T; while(T--)
    solve();
    return 0;
}