verify/rsq_bit.test.cpp

• View this file on GitHub
• Last update: 2019-12-05 03:16:14+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• lib/classes/binaryindexedtree.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/stdc++.h>
using namespace std;
using i64 = long;

#include "../lib/classes/binaryindexedtree.cpp"


signed main() {

    int n, q;
    scanf("%d%d", &n, &q);

    BIT<i64> b(n);
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        b.add(i, a);
    }
    for(int i = 0; i < q; ++i){
        int t, a, c;
        cin >> t >> a >> c;
        if(t == 0){
            b.add(a, c);
        }
        else{
            cout << b.sum(a, c) << endl;
        }
    }
}

#line 1 "verify/rsq_bit.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/stdc++.h>
using namespace std;
using i64 = long;

#line 1 "lib/classes/binaryindexedtree.cpp"
template <typename T>
struct BIT{
    vector<T> elm;
    BIT(int n, T init = T()) : elm(n + 1, init){
    }

    // [0, x)
    T sum(int x){
        T val = 0;
        for(; x > 0; x -= x & -x)
            val += elm[x];
        return val;
    }

    // [l, r)
    T sum(int l, int r){
        return sum(r) - sum(l);
    }

    void add(int x, T val){
        for(++x; x < elm.size(); x += x & -x)
            elm[x] += val;
    }
};

#line 8 "verify/rsq_bit.test.cpp"


signed main() {

    int n, q;
    scanf("%d%d", &n, &q);

    BIT<i64> b(n);
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        b.add(i, a);
    }
    for(int i = 0; i < q; ++i){
        int t, a, c;
        cin >> t >> a >> c;
        if(t == 0){
            b.add(a, c);
        }
        else{
            cout << b.sum(a, c) << endl;
        }
    }
}

Back to top page