segtree.cpp

//函数式线段树
struct Node {
    int sum;  
    Node *ls,*rs;
}pool[maxn<<5],*null,*pnow;
Node *newNode() {
    pnow->sum=0,pnow->ls=pnow->rs=null;
    return pnow++;
}
void addit(Node *&u,int l,int r,int pos,int v) {
    if(u==null) u=newNode();
    if(l==r) {
      u->sum+=v; return;
    }
    int m=l+((r-l)>>1);
    if(pos<=m)  addit(u->ls,l,m,pos,v);
    else        addit(u->rs,m+1,r,pos,v);
    u->sum=u->ls->sum+u->rs->sum;
}
int query(Node *&u,int l,int r,int L,int R) {
    if(u==null) u=newNode();
    if(L<=l && r<=R)  return u->sum;
    int m=l+((r-l)>>1);
    int res=0;
    if(R<=m)      res=query(u->ls,l,m,L,R);
    else if(L>m)  res=query(u->rs,m+1,r,L,R);
    else {
      res+=query(u->ls,l,m,L,m);
      res+=query(u->rs,m+1,r,m+1,R);
    }
    return res;
}
void init() {
    null=new Node();  null->sum=0; pnow=pool;
}