线段树学习（复习）笔记

# Part 1 ### 为什么要学线段树 扩展性强，可考性强，虽然常数大，码量大，但很常用，值得一学 # Part 2 ### 建树 - $1.$传入参数$l$,$r$,$p$(节点编号) - $2.$记录$tree[p].l=l;$ $tree[p].r=r;$ - $3.if$ $(l==r)$ 就初始化 $return;$ - $4.mid=(l+r)>>1;$ - $5.$左子树$build(l,mid,p*2);$ - $6.$右子树$build(mid+1,r,p*2+1);$ - $7.$用左右子树的答案更新自身答案 ##### $demo$ ```cpp void build(ll p,ll l,ll r) { ll mid; tree[p].l=l; tree[p].r=r; tree[p].cheng=1; if (l==r) { tree[p].ans=a[l]%Mod; //按情况也可以初始化其他 return; } mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); tree[p].ans=(tree[p*2].ans+tree[p*2+1].ans)%Mod; } ``` # Part 3 ### 基本操作 线段树所运用的常见情形有以下几种 - 1.单点修改，区间询问 - 2.区间修改，单点询问 - 3.区间修改，区间询问（在下一节中讨论） **注意线段树所维护的结果一定要满足区间可加性** ### 单点修改 ##### $demo$ ```cpp void change(int p,int x,int y) { int l,r,mid; l=tree[p].l; r=tree[p].r; if (l==r) { tree[p].ans+=y; return; } mid=(l+r)>>1; if (x<=mid) change(p*2,x,y); else change(p*2+1,x,y); tree[p].ans=tree[p*2].ans+tree[p*2+1].ans; } ``` ### 区间询问 ##### $demo$ ```cpp int query(int p,int x,int y) { int ans,l,r,mid; l=tree[p].l; r=tree[p].r; ans=0; if (x<=l&&y>=r) return tree[p].ans; mid=(l+r)>>1; if (x<=mid) ans+=query(p*2,x,y); if (y>mid) ans+=query(p*2+1,x,y); return ans; } ``` ### 区间修改 ##### $demo$ ```cpp void change(int p,int x,int y,int z) { int l,r,mid; l=tree[p].l; r=tree[p].r; if (x<=l&&y>=r) { tree[p].jia+=z; return; } mid=(l+r)>>1; if (x<=mid) change(p*2,x,y,z); if (mid<y) change(p*2+1,x,y,z); } ``` ## 单点询问 ##### $demo$ ```cpp int query(int p,int x) { int l,r,mid; l=tree[p].l; r=tree[p].r; if (l==r) return tree[p].jia; mid=(l+r)>>1; if (x<=mid) return query(p*2,x)+tree[p].jia; else return query(p*2+1,x)+tree[p].jia; } ``` 以上是区间数列加减的基本代码，可以根据实际情况调整 # Part 4 ### 区间修改，区间询问 一般有两种方法，标记下传和标记永久化 #### 标记下传（$lazytag$） 在区间上打标记，在维护和询问的过程中不断下放，维护答案，时间复杂度与树高同阶$O(log_n)$ #### $pushdown$ ##### $demo$ ```cpp void pushdown(int p) { if (!sum[p]) return; ans[p*2]+=sum[p]*(yy[p*2]-xx[p*2]+1); ans[p*2+1]+=sum[p]*(yy[p*2+1]-xx[p*2+1]+1); sum[p*2]+=sum[p]; sum[p*2+1]+=sum[p]; sum[p]=0; } ``` #### 区间修改 ##### $demo$ ```cpp void jia(ll p,ll x,ll y,ll z) { ll l,r,mid; l=tree[p].l; r=tree[p].r; if (x<=l&&y>=r) { tree[p].jia+=z; tree[p].ans+=z*(r-l+1); return; } pushdown(p); mid=(l+r)>>1; if (l<=mid) jia(p*2,x,y,z); if (r>mid) jia(p*2+1,x,y,z); tree[p].ans=(tree[p*2].ans+tree[p*2+1].ans); } ``` #### 区间询问 ##### $demo$ ```cpp ll query(ll p,ll x,ll y) { pushdown(p); ll l,r,mid,ans; ans=0; l=tree[p].l; r=tree[p].r; if (x<=l&&y>=r) return tree[p].ans; mid=(l+r)>>1; if (l<=mid) ans+=query(p*2,x,y); if (r>mid) ans+=query(p*2+1,x,y); return ans; } ``` ------------ #### 标记永久化 标记永久化的原理简单来说就是修改时一路更改被影响到的点，询问时则一路累加路上的标记，从而省去下传标记的操作。但局限性比较大，不如标记下传的适用范围广。 #### 区间修改 ##### $demo$ #### 区间询问 ##### $demo$