88962


セグメント木での累積和の計算を入力してみましたが意図した内容と合いません。  
出力される内容をresではなく、datb[k] * (r - l) + datc[k]の内容のように正しくしたいです。

[code]

    #include <iostream>
    using namespace std;
    typedef long long ll;
    const int MAX_N = 100000;
    const int MAX_Q = 100000;
    const int DAT_SIZE = (1 << 18) - 1;
    int N, Q;
    int A[MAX_N];
    char T[MAX_Q];
    int L[MAX_Q], R[MAX_Q], X[MAX_Q];
    ll datb[DAT_SIZE], datc[DAT_SIZE];
    void input() {
        cin >> N >> Q;
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }
        for (int i = 0; i < Q; i++) {
            cin >> T[i];
            if (T[i] == 'C') {
                cin >> L[i] >> R[i] >> X[i];
            }
            else {
                cin >> L[i] >> R[i];
            }
        }
    }
    void add(int a, int b, int x, int k, int l, int r) {
        if (a <= l && r <= b) {
            datb[k] += x;
        }
        else if (l < b && a < r) {
            datc[k] += (min(b, r) - max(a, l)) * x;
            add(a, b, x, k * 2 + 1, l, (l + r) / 2);
            add(a, b, x, k * 2 + 2, (l + r) / 2, r);
        }
    }
    ll sum(int a,int b,int k,int l,int r) {
        if (b <= l || r <= a) {
            return 0;
        }
        else if (a <= l && r <= b) {
            return datb[k] * (r - l) + datc[k];
        }
        else {
            ll res = (min(b, r) - max(a, l)) * datb[k];
            res += sum(a, b, k * 2 + 1, l, (l + r) / 2);
            res += sum(a, b, k * 2 + 2, (l + r) / 2, r);
            return res;
        }
    }
    void solve() {
        for (int i = 0; i < N; i++) {
            add(i, i+1, A[i], 0, 0, N);
        }
        for (int i = 0; i < Q; i++) {
            if (T[i] == 'C') {
                add(L[i], R[i]+1, X[i], 0, 0, N);
            }
            else {
                printf("%lld\n", sum(L[i], R[i]+1, 0, 0, N));
            }
        }
    }
    int main()
    {
        input();
        solve();
        return 0;
    }
    
[/code]

入力

[code]

    10 5
    1 2 3 4 5 6 7 8 9 10
    Q 4 4
    Q 1 10
    Q 2 4
    C 3 6 3
    Q 2 4
    
[/code]

出力

[code]

    5 
    54
    12 
    18
    
[/code]

出力内容を次のようにしたい。

[code]

    4
    55
    9
    15
    
[/code]


CC BY-SA 4.0
2022-05-19T13:25:16.567
88925
2022-05-21T06:27:23.700
2022-05-21T05:44:09.890
50767
50767
question
c++ アルゴリズム
蟻本P.164の問題のセグメント木での累積和の計算で意図した内容と異なる内容が出力される。


入力のインデックスが1始まりで、セグメント木のインデックスが0始まりってだけでは?

[code]

    void solve() {
        for (int i = 0; i < N; i++) {
            add(i, i + 1, A[i], 0, 0, N);
        }
        for (int i = 0; i < Q; i++) {
            if (T[i] == 'C') {
                add(L[i]-1, R[i], X[i], 0, 0, N);
            }
            else {
                printf("%lld\n", sum(L[i]-1, R[i], 0, 0, N));
            }
        }
    }
    
[/code]


CC BY-SA 4.0
2022-05-21T06:27:23.700
88962
2022-05-21T06:27:23.700
43506
88925
answer