线段树

FIRST:

线段树是干嘛用的
给定n个数，支持操作：
①单点修改，单点查询。
②区间修改，单点查询。
③单点修改，区间查询。
④区间修改，区间查询。
时间复杂度要求小于n^2。

动态开点

void update (int &root,int l,int r,int t,int x) //当前节点编号，当前节点对应的区间，要修改的叶子结点编号，增加的值 { if (!root) root=++cnt; 
  sum[root]+=x; if (l==r) return; int mid=(l+r)/2; if (t<=mid) update(L[root],l,mid,t,x); else update(R[root],mid+1,r,t,x);
} //Ex1

	//update(root,1,9,5,3) //这棵线段树的叶子结点总共有9个，把第5个叶子增3 update(root,1,9,4,4) 

1.如何查询？

int query (int &root,int l,int r,int x,int y) //当前节点在root，root对应的区间是[l,r]，要查[x,y]的和 { if (l==x && r==y) return sum[root]; int mid=(l+r)/2,suml=0,sumr=0; if (x<=mid) suml=query(L[root],l,mid,x,min(mid,y)); //要查的区间的左端点被左儿子区间包含的时候  if (y>mid) sumr=query(R[root],mid+1,r,max(mid+1,x),y); return suml+sumr;
} 
//cout<<query(root,1,9,3,5) //查询[3,5]的和

问题2

区间修改，单点查询如何进行区间操作？
答：lazy tag！

void update (int &root,int l,int r,int p,int q,int x) //当前节点编号，当前节点对应的区间，要修改的区间编号，增加的值  { if (!root) root=++cnt; 
     sum[root]+=x*(l~r 和 p~q的交); if (l==p && r==q) {tag[root]+=x; return;} int mid=(l+r)/2; if (p<=mid) update(L[root],l,mid,p,min(q,mid),x); if (q>mid) update(R[root],mid+1,r,max(mid+1,p),q,x);
}
//update(root,1,9,5,7,3) //这棵线段树的叶子结点总共有9个，把编号为5~7个叶子增3

如何查询？

int query (int &root,int l,int r,int x,int y) // 当前节点在root，root对应的区间是[l,r]，要查[x,y]的和  { if (l==x && r==y) return sum[root];
    Down(root,l,r); int mid=(l+r)/2,suml=0,sumr=0; if (x<=mid) suml=query(L[root],l,mid,x,min(mid,y)); //要查的区间的左端点被左儿子区间包含的时候   if (y>mid) sumr=query(R[root],mid+1,r,max(mid+1,x),y); return suml+sumr;
}
    // cout<<query(root,1,9,3,5)； //查询[3,5]的和  int Down(int x,int l,int r) //为x的节点，x的区间是[l,r]，进行标记下传  { if (!L[x]) L[x]=++cnt; if (!R[x]) R[x]=++cnt;
    tag[L[x]] += tag[x];  tag[R[x]] += tag[x];
    sum[L[x]] += tag[x] * (左儿子节点个数);
    sum[R[x]] += tag[x] * (..);
    tag[x]=0;
}