线段树模板

第一步先建造树

void build(int node,int L,int R) { if(L==R) tree[node]=a[L]; else { int mid=(L+R)/2; build(node*2,L,mid);//建立左子树 build(node*2+1,mid+1,R);//建立右子树 tree[node]=tree[node*2]+tree[node*2+1]; } }

1.单点修改，区间查询。

void update(int node,int L,int R,int x,int y)//修改 { if(L==R) tree[node]+=y; else { int mid=(L+R)/2; if(x<=mid) update(node*2,L,mid,x,y); else update(node*2+1,mid+1,R,x,y); tree[node]=tree[node*2]+tree[node*2+1]; } } void query(int node,int L,int R,int x,int y)//查询 { if(x<=L&&y>=R) sum+=tree[node]; else { int mid=(L+R)/2; if(x<=mid) query(node*2,L,mid,x,y); else query(node*2+1,mid+1,R,x,y); } }

2.区间修改，单点查询 区间修改要用到懒惰标记，lazy数组。

void lazytree(int node,int l)//懒惰标记 { if(lazy[node]) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; tree[node*2]+=lazy[node]*(l-l/2); tree[node*2+1]+=lazy[node]*(l/2); lazy[node]=0; } } void update(int node,int L,int R,int x,int y,int z)//修改 { if(x<=L&&y>=R) { tree[node]+=(R-L+1)*z; lazy[node]+=z; } else { lazytree(node,R-L+1); int mid=(L+R)/2; if(x<=mid) update(node*2,L,mid,x,y,z); if(y>mid) update(node*2+1,mid+1,R,x,y,z); tree[node]=tree[node*2]+tree[node*2+1]; } } void query(int node,int L,int R,int x)//查询 { if(L==R) printf("%d\n",tree[node]); else { lazytree(node,R-L+1); int mid=(L+R)/2; if(x<=mid) query(node*2,L,mid,x); else query(node*2+1,mid+1,R,x); } }

3.区间修改区间查询

void lazytree(int node,int l) { if(lazy[node]) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; tree[node*2]+=lazy[node]*(l-l/2); tree[node*2+1]+=lazy[node]*(l/2); lazy[node]=0; } } void update(int node,int L,int R,int x,int y,int z)//修改 { if(x<=L&&y>=R) { tree[node]+=(R-L+1)*z; lazy[node]+=z; } else { lazytree(node,R-L+1); int mid=(L+R)/2; if(x<=mid) update(node*2,L,mid,x,y,z); if(y>mid) update(node*2+1,mid+1,R,x,y,z); tree[node]=tree[node*2]+tree[node*2+1]; } } void query(int node,int L,int R,int x,int y)//查询 { if(x<=L&&y>=R) sum+=tree[node]; else { lazytree(node,R-L+1); int mid=(L+R)/2; if(x<=mid) query(node*2,L,mid,x,y); if(y>mid) query(node*2+1,mid+1,R,x,y); } }