test/library_checker/data_structure/point_add_range_sum.test.cpp

• View this file on GitHub
• Last update: 2024-11-15 16:06:01+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• Binary Indexed Tree (lib/data_structure/binary_indexed_tree.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <iostream>

#include "../../../lib/data_structure/binary_indexed_tree.hpp"

using namespace std;

int main(){
    int n, q; cin >> n >> q;
    BinaryIndexedTree<long long> BIT(n);
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        BIT.add(i, a);
    }
    while(q--){
        int t; cin >> t;
        if(t == 0){
            int p, x; cin >> p >> x;
            BIT.add(p, x);
        }else{
            int l, r; cin >> l >> r;
            cout << BIT.sum(l, r) << "\n";
        }
    }
}

#line 1 "test/library_checker/data_structure/point_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <iostream>

#line 2 "lib/data_structure/binary_indexed_tree.hpp"

/**
 * @brief Binary Indexed Tree
 * @docs docs/data_structure/binary_indexed_tree.md
 */

#include <vector>

template <typename T>
struct BinaryIndexedTree{
    int N;
    std::vector<T> BIT;
    BinaryIndexedTree(const int N) : N(N), BIT(N + 1, 0){
    }

    T get(int i){
        return sum(i + 1) - sum(i);
    }

    void add(int i, T x){
        i++;
        while(i <= N){
            BIT[i] += x;
            i += i & -i;
        }
    }

    T sum(int i) const {
        T ans = 0;
        while(i > 0){
            ans += BIT[i];
            i -= i & -i;
        }
        return ans;
    }

    T sum(int L, int R) const {
        return sum(R) - sum(L);
    }

    int lower_bound(T x) const {
        if(x <= 0){
            return 0;
        } else{
            int v = 0, r = 1;
            while(r < N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len < N && BIT[v + len] < x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    int upper_bound(T x) const {
        if(x < 0){
            return 0;
        } else{
            int v = 0, r = 1;
            while(r <= N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len <= N && BIT[v + len] <= x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    T operator [](int i) const {
        return sum(i, i + 1);
    }
};
#line 5 "test/library_checker/data_structure/point_add_range_sum.test.cpp"

using namespace std;

int main(){
    int n, q; cin >> n >> q;
    BinaryIndexedTree<long long> BIT(n);
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        BIT.add(i, a);
    }
    while(q--){
        int t; cin >> t;
        if(t == 0){
            int p, x; cin >> p >> x;
            BIT.add(p, x);
        }else{
            int l, r; cin >> l >> r;
            cout << BIT.sum(l, r) << "\n";
        }
    }
}

Back to top page