各类线段树模板

1.用数组维护线段树，可实现单点修改和区间查询。

int tree[MAXN*4];
int n；                                                  //区间长度，若非2^n,需扩充至2^n
void add(int i,int num){                                //i表示要修改的单点对应的线段树节点的编号，线段树                                                                              节点由上至下，由左到右从1开始编号。查询函数同。
    while(i>=1){
        tree[i]+=num;
        i/=2;
    }
}
int query(int i,int j){
    if (j<i) return 0;
    int cnt=0;
    if (i%2!=0){
        cnt+=tree[i];
        i++;
    }
    if (j%2==0){
        cnt+=tree[j];
        j--;
    }
    return cnt+query(i/2,j/2);
}