②n=9
二.线段树的构造与实现
1.建树与维护
根据线段树的性质，我们可以得到一个节点的左儿子和右儿子的表示方法（上面有提QwQ）
inline ll ls(ll x)//左儿子 { return x<<1;//相当于x*x } inline ll rs(ll x)//右儿子 { return (x<<1)|1;//相当于x*2+1 }
于是就有了维护的代码：
inline void push_up_sum(ll p)//向上维护区间和 { ans[p]=ans[ls(p)]+ans[rs(p)]; } inline void push_up_min(ll p)//向上维护区间最小值 { ans[p]=min(ans[ls(p)],ans[rs(p)]); } inline void push_up_max(ll p)//向上维护区间最大值 { ans[p]=max(ans[ls(p)],ans[rs(p)]); }
需要注意的是，这里是从下往上维护父子节点的逻辑关系，因为当你一个子节点改变了之后，它所有的父亲节点都需要改变。所以开始递归之后必然是先去整合子节点的信息，再向它们的祖先反馈整合之后的信息。
所以对于建树，由于二叉树的结构特点，我们可以选择递归建树，并且在递归的过程中要注意维护父子关系
void build(ll p,ll l,ll r)//p 根节点,l 区间左端点,r 区间右端点 { tag[p]=0;//建树时顺便把懒惰标记清零(这个后面会提到) if(l==r)//如果左右端点相等,就说明已经到达了叶子结点 { ans[p]=a[l]; return ; } ll mid=(l+r)>>1;//左右子树分别递归建树 build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p);//记得维护父子关系 }
我们已经有了一棵线段树，但是现在并不能对它进行什么操作，它目前还并没有什么卵用
2.区间修改
假如我们要修改一个区间[l,r]内的值，我们发现由于二叉树的结构特点，l和r很可能不在同一个节点上，这时候怎么办？
区间拆分了解一下
区间拆分是线段树的核心操作,我们可以将一个区间[a, b]拆分成若干个节点,使得这些节点代表的区间加起来是[a, b],并且相互之间不重叠.
所有我们找到的这些节点就是”终止节点”.
区间拆分的步骤
从根节点[1, n]开始，考虑当前节点是[L, R].
如果[L, R]在[a, b]之内,那么它就是一个终止节点.
否则,分别考虑[L, Mid],[Mid + 1, R]与[a, b]是否有交,递归两边继续找终止节点
举个栗子：
比如我们要从[1,10]中拆分出[2,8]这个区间
还是挺直观的吧QwQ
这其实是一种分块的思想
分块的思想是通过将整个序列分为有穷个小块，对于要查询的一段区间，总是可以整合成k个所分块与m个单个元素的信息的并
所以我们应该充分利用区间拆分的性质，思考在终止节点要存什么信息，如何快速维护这些信息，不要每次一变就到最底层
那么对于区间操作，我们引入一个东西——懒标记(lazy tag)。那这个东西“lazy”在什么地方呢？
我们发现原本的区间修改需要通过改变最下的叶子结点，然后不断向上递归来修改祖先节点直至到达根节点，时间复杂度最多可以到O(n logn)的级别。
但是当我们用了懒标记后，时间复杂度就降低到了O(log n)的级别甚至更低
懒标记怎么用？
如果整个区间都被操作，就把懒标记记录在公共祖先节点上，如果只修改了一部分，就记录在这部分的公共祖先上，如果只修改了自己的话，就只改变自己
然后，如果我们采用这种方式优化的话，我们需要在每一次区间查询修改时pushdown一次，以免重复冲突
那么怎么传导pushdown呢？
开始回溯是执行pushup，因为是向上传导信息；如果我们想要他向下更新，就调整顺序，在向下递归的时候pushdown
代码：
inline void f(ll p,ll l,ll r,ll k) { tag[p]=tag[p]+k; ans[p]=ans[p]+k*(r-l+1); //由于是这个区间统一改变，所以ans数组要加元素个数 } //f函数的唯一目的，就是记录当前节点所代表的区间 inline void push_down(ll p,ll l,ll r) { ll mid=(l+r)>>1; f(ls(p),l,mid,tag[p]); f(rs(p),mid+1,r,tag[p]); tag[p]=0; //不断向下递归更新子节点 } inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k) { //nl,nr为要修改的区间 //l,r,p为当前节点所存储的区间以及节点的编号 //k为要增加的值 if(nl<=l&&r<=nr) { ans[p]+=k*(r-l+1); tag[p]+=k; return; } push_down(p,l,r); //回溯之前（也可以说是下一次递归之前，因为没有递归就没有回溯） //由于是在回溯之前不断向下传递，所以自然每个节点都可以更新到 ll mid=(l+r)>>1; if(nl<=mid) update(nl,nr,l,mid,ls(p),k); if(nr>mid) update(nl,nr,mid+1,r,rs(p),k); push_up(p); //回溯之后 }
对于复杂度而言，由于完全二叉树的深度不超过logn，那么单点修改显然是O(logn)的，区间修改的话
原文：https://www.cnblogs.com/lcezych/p/10964489.html