在清北学堂的时候，老师讲了一下，没太搞懂，回来自己理解了一下
*******线段树*******线段树O(log(n))个区间覆盖L~R信息每层最多选两个区间mx区间最大值int n;int a[];int mx[];//o是当前节点编号，当前表示的区间范围//就是用数组实现树，mx代表o区间内最大值void build(int o,int l,int r){ if(l==r){ mx[o] = a[l];//区间内只有一个数，当然是它了 }else{ int mid=(l+r)/2; build(o*2,l,mid);//先把两个子区间的最大值求出来，再取最大 build(o*2+1,mid+1,r); mx[o]=max(mx[o*2],mx[o*2+1]); }}build(1,1,n)//mx[1]是整个a数组里最大的******分界线*******查询操作：// o结点编号，l,r线段树的区间，L,R查询的区间int ask(int o,int l,int r,int L,int R){ if(l==L&&r==R){ return mx[o];//已经找到对应区间 }else{ down(o);//下方标记，先不管 int mid=(l+r)/2; if(R<=mid) return ask(o*2,l,mid,L,R); else if(L>mid)return ask(o*2+1,mid+1,r,L,R); else return max(ask(o*2,l,mid,L,mid), ask(o*2+1,mid+1,r,mid+1,R))//没有恰好对应的区间，只能将其一分为二 }}ask(1,1,n,L,R);******分界线*******// 单点修改// l,r线段树节点表示的区间，pos修改位置（一直不变），w新的值（也不变）//其实这几个操作和前面差不多void modify(int o,int l,int r,int pos,int w){ if(l==r){ mx[o] = w; } else { down(o); int mid=(l+r)/2; if(pos<=mid){ //左边 modify(o*2,l,mid,pos,w); }else{ //右边 modify(o*2+1,mid+1,r,pos,w); } mx[o]=max(mx[o*2],mx[o*2+1]);//快速合并 }}******分界线*******// 新操作： 给位置在L~R的数字+x，直接操作没有线段树的意义Lazy 思想如果一个区间被区间修改操作整个覆盖：不用递归修改，建立一个lazy标记如果真正访问下面节点，再下放（dawn）标记// o, l,r表示当前区间，L,R表示要修改的区间,表示要加的值int lazy[];//存放标记void down(int o){//假如真正查询到了，才真正进行下放（但每次都需要判断） if(lazy[o]!=0){ mx[o*2]+=lazy[o]; mx[o*2+1]+=lazy[o]; lazy[o*2]+=lazy[o]; lazy[o*2+1]+=lazy[o]; lazy[o]=0; //清空标记 }}void add(int o,int l,int r,int L,int R,int w){ if(l==L&&r==R){ mx[o]+=w; lazy[o]+=w;//对于子区间来说没有下放的标记， }else{ //下放标记，貌似所以线段树的操作都有这一步 down(o);//让子区间都加上 int mid=(l+r)/2; if(R<=mid) add(o*2,l,mid,L,R,w);//左 else if(L>mid) add(o*2+1,mid+1,r,L,R,w);//右 else{ add(o*2,l,mid,L,mid,w); add(o*2+1,mid+1,r,mid+1,R,w)); } } mx[o]=max(mx[o*2],mx[o*2+1]);//因为子区间大小改变，mx要重新求}
转载于:https://www.cnblogs.com/DukeLv/p/8454504.html
