动态开点线段树模板

const int M =1e5+5; 
struct node{int sum=0;int l=0,r=0;
}tr[M*30];
#define ls(x) (tr[x].l)
#define rs(x) (tr[x].r)
#define sum(x) (tr[x].sum)
int tot;
void pull(int x){sum(x)=sum(ls(x))+sum(rs(x));}
void push(int x){if(!ls(x))ls(x)=++tot;if(!rs(x))rs(x)=++tot;
}
int qr(int x,int l,int r,int L,int R){if(L<=l&&r<=R)return sum(x);if(l>R || r<L)return 0;push(x);int mid = (l+r-1)>>1;return qr(ls(x),l,mid,L,R)+qr(rs(x),mid+1,r,L,R);
}
void change(int x,int l,int r,int pos,int k){if(l==r){sum(x)+=k;return;}int mid =(l+r-1)>>1;push(x);if(pos<=mid)change(ls(x),l,mid,pos,k);else change(rs(x),mid+1,r,pos,k);pull(x);
}