Test/yosupo-judge/BinaryIndexedTree.test.cpp

View this file on GitHub
Last update: 2021-06-18 21:14:35+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

Code

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

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

#include"../../Other/Template.cpp"
#include"../../DataStructure/BinaryIndexedTree.cpp"

int main() {
    int N,Q;
    cin >> N >> Q;
    vector<long long> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    BinaryIndexedTree<long long> bit(N);
    for(int i = 0;i < N;i++) {
        bit.add(i,vec.at(i));
    }
    for(int i = 0;i < Q;i++) {
        int l,r;
        cin >> l >> r;
        cout << bit.sum(l,r) << endl;
    }
}

#line 1 "Test/yosupo-judge/BinaryIndexedTree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

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

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "DataStructure/BinaryIndexedTree.cpp"
template <typename T>
class BinaryIndexedTree {
    int N;
    vector<T> bit;

    T sum_sub(int a) {
        a++;
        T ret = 0;
        if(a == 0) return ret;
        while(a > 0) {
            ret += bit[a];
            a -= a & -a;
        }
        return ret;
    }

public:

    BinaryIndexedTree(int n): N(n) {
        bit.assign(++n,0);
    }

    void add(int i,T x) {
        i++;
        if(i == 0) return;
        while(i < bit.size()) {
            bit[i] += x;
            i += i & -i;
        }
    }

    T sum(int l,int r) {
        return sum_sub(r - 1) - sum_sub(l - 1);
    }
};
#line 8 "Test/yosupo-judge/BinaryIndexedTree.test.cpp"

int main() {
    int N,Q;
    cin >> N >> Q;
    vector<long long> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    BinaryIndexedTree<long long> bit(N);
    for(int i = 0;i < N;i++) {
        bit.add(i,vec.at(i));
    }
    for(int i = 0;i < Q;i++) {
        int l,r;
        cin >> l >> r;
        cout << bit.sum(l,r) << endl;
    }
}