segmentTree.cpp

#include <iostream>
#include <vector>
using namespace std;
void build(const vector<int>&v, vector<int>&seg, int start ,int end , int node){
    if ( start == end){
        seg.at(node)=v.at(start);
        return; 
    }
    int mid = (start + end) / 2;
    build(v,seg,start , mid , 2*node);
    build(v,seg,mid+1,end, 2*node+1);
    seg.at(node ) = seg.at(2*node)  + seg.at(2*node+1);
    return;
}
int query(const vector<int>&seg, int start , int mid , int qs, int qe, int node){
    if( qs > end or qe < start)
        return 0;
    if( start >= qs and end <= qe)
        return seg.at(node);
    int mid = (start + end) / 2;
    int lans = query(seg, start , mid , qs, qe, 2*node);
    int rans = query(seg, mid+1, end, qs, qe, 2*node+1);
    return (lans + rans);
}
void updateNode(vector<int>&seg, int start, int end, int qnode , int value , int node){
    if(qnode > end and qnode < start ){
        return;
    }
    if(start == end){
        seg.at(node) = value;
        return ;
    }
    int mid = ( start + end) /2;
    updateNode( seg, start , mid, qnode , value, 2*node);
    updateNode( seg, mid+1, end , qnode, value , 2*node+1);
    seg.at(node) = seg.at(2*node) + seg.at(2*node+1);
}
int main(void){
    vector<int>v;
    for(int i=0; i<1000; ++i)
        v.push_back(i);
    v.shrink_to_fit();
    int x = (int)ceil(log2(v.size()));
    int size = 2*(int)pow(2,x)-1;
    vector<int>seg(size);
    build(v,seg,0,v.size()-1,1);
    cout<<"build"<<endl;
    int query;
    cin>>query;
    while(query--){
        int qs, qe;
        cin>>qs>>qe;
        cout<<query(seg,0,v.size()-1,qs,qe,1)<<endl;
    }
    return 0;
}