SYZOJ - [線段樹]模闆題2(樹狀數組)

題目連結:https://syzoj.com/problem/510

記憶體限制：256 MiB 時間限制：5000 ms

題目描述

這是一道模闆題。

給定數列 a[1],a[2],…,a[n]，你需要依次進行 q 個操作，操作有兩類：

• 1 l r x

  ：給定 l,r,x，對于所有 i∈[l,r]，将 a[i] 加上 x(換言之，将 a[l],a[l+1],…,a[r] 分别加上 x);

• 2 l r

  ：給定 l,r，求 

  

   的值(換言之，求 a[l]+a[l+1]+⋯+a[r] 的值)。

輸入格式

第一行包含 2 個正整數 n,q，表示數列長度和詢問個數。保證 1≤n,q≤10^6​​。

第二行 n 個整數 a[1],a[2],…,a[n]，表示初始數列。保證 ∣a[i]∣≤10^6​​。

接下來 q 行，每行一個操作，為以下兩種之一：

• 1 l r x

  ：對于所有 i∈[l,r]，将 a[i] 加上 x；

• 2 l r

  ：輸出 

  

   的值。

保證 1≤l≤r≤n, ∣x∣≤10^6​​。

輸出格式

對于每個 

2 l r

 操作，輸出一行，每行有一個整數，表示所求的結果。

樣例輸入

5 10

2 6 6 1 1

2 1 4

1 2 5 10

2 1 3

2 2 3

1 2 2 8

1 2 3 7

1 4 4 10

2 1 2

1 4 5 6

2 3 4

樣例輸出

資料範圍與提示

解題思路

#include <bits/stdc++.h>
using namespace std;
long long bits_0[1000005], bits_1[1000005], n;
int lowbit(int x) {
    return x & (-x);
}
void Update(long long *bits, int i, long long k) {
    while (i <= n) {
        bits[i] += k;
        i += lowbit(i);
    }
}
long long PrefixSum(long long *bits, int i) {
    long long cnt = 0;
    while (i > 0) {
        cnt += bits[i];
        i -= lowbit(i);
    }
    return cnt;
}
long long RangeSum(int left, int right) {
    long long ans = PrefixSum(bits_0, right) * right + PrefixSum(bits_1, right);
    return ans - PrefixSum(bits_0, left - 1) * (left - 1) - PrefixSum(bits_1, left - 1);
}
int main() {
    int q, delta, judge, left, right;
    while (~scanf("%d%d", &n, &q)) {
        memset(bits_0, 0, sizeof(bits_0));
        memset(bits_1, 0, sizeof(bits_1));
        for (int i = 1; i <= n; i++) {
            scanf("%d", &delta);
            Update(bits_1, i, delta);
        }
        while (q--) {
            scanf("%d", &judge);
            if (judge - 1) {
                scanf("%d%d", &left, &right);
                printf("%lld\n", RangeSum(left, right));
            }
            else {
                scanf("%d%d%d", &left, &right, &delta);
                Update(bits_0, left, delta);
                Update(bits_1, left, 1ll * -delta * (left - 1));
                Update(bits_0, right + 1, -delta);
                Update(bits_1, right + 1, 1ll * delta * right);
            }
        }
    }
    return 0;
}