verify/aoj/binary-indexed-tree.test.cpp

• View this file on GitHub
• Last update: 2023-03-19 23:21:06-07:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

• segment-tree/binary-indexed-tree.hpp

Code

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

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

#include "../../segment-tree/binary-indexed-tree.hpp"

int main(){
    int N,Q;cin>>N>>Q;
    BinaryIndexedTree bit(N);

    while(Q--){
        int com,x,y;cin>>com>>x>>y;

        if(com==0)bit.add(x-1,y);
        else cout<<bit.sum(x-1,y)<<endl;
    }
}

#line 1 "verify/aoj/binary-indexed-tree.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

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

#line 2 "segment-tree/binary-indexed-tree.hpp"
struct BinaryIndexedTree{
    // 0-indexed
    int size;
    std::vector<long long> tree={0};

    BinaryIndexedTree(int n,std::vector<long long> l={}):size(n){
        if(l.empty()){
            for(int i=0;i<size;i++)tree.push_back(0);
        }else{
            for(long long i:l){
                tree.push_back(i);
            }
            std::vector<long long> c(n+1,0);
            for(int i=0;i<size;i++){
                c[i+1]=l[i]+c[i];
            }
            for(int x=1;x<=size;x++){
                tree[x]=c[x]-c[x-(x&-x)];
            }
        }
    }

    long long _sum(int r){
        //sum(t[0,r))
        if(r==0)return 0;
        long long s=0;
        while(r>0){
            s+=tree[r];
            r-=r&-r;
        }
        return s;
    }

    long long sum(int l,int r){
        //sum(t[l,r))
        return _sum(r)-_sum(l);
    }

    void add(int i,long long x){
        //t[i]+=x
        i++;
        while(i<=size){
            tree[i]+=x;
            i+=i&-i;
        }
    }
};
#line 7 "verify/aoj/binary-indexed-tree.test.cpp"

int main(){
    int N,Q;cin>>N>>Q;
    BinaryIndexedTree bit(N);

    while(Q--){
        int com,x,y;cin>>com>>x>>y;

        if(com==0)bit.add(x-1,y);
        else cout<<bit.sum(x-1,y)<<endl;
    }
}

Back to top page