test/structure/BIT.aoj_DSL_2_B.test.cpp

View this file on GitHub
Last update: 2022-08-03 17:09:04+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

BIT (Binary Indexed Tree) (structure/bit.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#include <iostream>
#include "structure/bit.hpp"

int main(){
    int N, Q;
    std::cin >> N >> Q;
    BIT<long long> bt(N);
    for(int i=0; i<Q; i++){
        int com, x, y;
        std::cin >> com >> x >> y;
        if(com == 0){
            bt.add(x, y);
        }else{
            std::cout << bt.sum(y) - bt.sum(x-1) << std::endl;
        }
    }
}

#line 1 "test/structure/BIT.aoj_DSL_2_B.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#include <iostream>
#line 2 "structure/bit.hpp"
#include <vector>


template <typename T>
struct BIT {
    int N;
    std::vector<T> bit;
    BIT(size_t sz) : N(sz + 2), bit(N, 0) {}

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

    T sum(int i){
        T ret = 0;
        for(int idx = i; idx > 0; idx -= idx & -idx){
            ret += bit[idx];
        }
        return ret;
    }
};
#line 5 "test/structure/BIT.aoj_DSL_2_B.test.cpp"

int main(){
    int N, Q;
    std::cin >> N >> Q;
    BIT<long long> bt(N);
    for(int i=0; i<Q; i++){
        int com, x, y;
        std::cin >> com >> x >> y;
        if(com == 0){
            bt.add(x, y);
        }else{
            std::cout << bt.sum(y) - bt.sum(x-1) << std::endl;
        }
    }
}