线段树

线段树是什么？

线段树是一种~~能让你代码强行增加50行的极容易爆炸的万金油~~数据结构，用于优雅暴力地解决对一个区间上满足区间可加性（即可由两个子区间的信息得到当前区间信息） 的 区间修改和区间查询问题。

结构：

将区间划分为左端点到中点（即左子区间）和中点+1到右端点（即右子区间）的两个子区间，然后对两个子区间继续划分，直到划分到单个元素（即左端点=右端点）

示意图：

不难看出线段树除了最下面一层，其他的部分一定是一颗完全二叉树，这意味着整棵树可以使用“父子二倍法”（左儿子编号为父亲编号 $\times$ 2，右儿子编号为父亲编号 $\times$ 2 $+$ 1）存储在一个数组中。同时，因为还要考虑到最后一层，数组的大小应开到n $\times$ 4大小。

线段树的一个很重要的性质就是一棵[1~n]的线段树的深度最大为 $log_2 n+1$,这也意味着线段树可在$O(logn)$的时间复杂度内完成所有操作。

实现

以洛谷P3372 【模板】线段树 1的维护最大值为例
首先，我们给线段树中每个元素一个sum变量存储该元素代表区间的区间和，叶子结点的sum是原数组当前位置的值，非叶节点的sum是其左右子节点sum的和，如当原数组为

时，对应的线段树为

节点结构体：


struct segmenttree{
  int l,r,sum,add;
  #define l(x) tree[x].l //当前区间左端点
  #define r(x) tree[x].r //当前区间右端点
  #define sum(x) tree[x].sum //区间和
  #define add(x) tree[x].add //延迟标记（这个后面会讲）
}tree[maxn];

操作

操作有递归和非递归两种形式，递归式相对于非递归式更直观，因此这里讲解递归式。

非递归式和递归式本同末异，考试时按照数据规模而定。

建树：

按照之前提到的定义，从根节点([1~n])向左右两边递归，递归到叶子结点就将该节点sum设为其在原数组中对应的值，回溯时将当前节点的sum设为其左右子节点sum的和。

代码：


void build(int p,int l,int r)
{
  l(p)=l;r(p)=r; //设置端点
  if(l==r) { sum(p)=num[l]; return;} //如果是叶子节点
  int mid=((l+r)>>1); //位运算，右移1位相当于/2，左移同理
  build(p<<1,l,mid); //向左递归
  build(p<<1|1,mid+1,r) //向右递归，一个偶数|1相当于+1
}

复杂度为$O(nlogn)$

区间查询：

设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$ ,则

当 $l \leq l_1$ 且 $r \geq r_1$时直接返回当前区间的sum,因为当前区间已经涵盖了子区间的全部信息。
当 $l \leq mid$时，向左递归，$r_1=mid$（此时查询区间一定涵盖左子区间的一部分）
当 $r > mid$时，向右递归，$l_1=mid+1$ （此时查询区间一定涵盖右子区间的一部分）

代码：


int query(int p,int l,int r)
{
  if(l<=l(p) && r>=r(p)) return sum(p); //完全包含
  int mid=((l(p)+r(p))>>1);
  int ans=0;
  if(l<=mid) ans+=query(p<<1,l,mid); //向左递归，累加左子树答案
  if(r>mid) ans+=query(p<<1|1,mid+1,r); //向右递归，累加左子树答案
  return ans;
}

复杂度为$O(logn)$

区间修改与延迟标记：

当进行区间修改时，我们依然可以设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$，同时查询操作也满足这两条性质：

当 $l \leq mid$时，向左递归，$r_1=mid$（此时查询区间一定涵盖左子区间的一部分）
当 $r > mid$时，向右递归，$l_1=mid+1$ （此时查询区间一定涵盖右子区间的一部分）

但当出现完全覆盖的情况时，事情就变得不那么简单了，一个一个深入更新会使单次修改的复杂度高达 $O(n)$,这是我们所无法接受的。这时，我们就要引入延迟标记。

试想一下，如果你花费很大的代价更新了节点p的子树，但在之后的查询中却根本没有访问到它们，那更新p的子树岂不是白费力气？因此，我们可以在区间修改出现“完全覆盖”情况时也直接返回，但要给当前节点打上一个代表“当前节点已被更新，但其子节点尚未被更新”的延迟标记（这里取名add）。（如果操作是相容的（如加法），那在打标记前无需下传原来的标记。如果操作是不相容的（如赋值），那在打标记前需下传原来的标记。）

在以后的查询操作中，如果遇到了有延迟标记的节点，便将其的两个子节点更新并打上延迟标记，并擦除当前节点的延迟标记（即将延迟标记下传一层），这样就减少了大量无用的更新操作 ~~（虽然本质上依旧是暴力）~~。

代码：


void spread(int p) //下传标记
{
  if(add(p))
  {
    add(p<<1)+=add(p);
    add(p<<1|1)+=add(p);
    sum(p<<1)+=add(p)*(r(p<<1)-l(p<<1)+1); //区间和增量=数值增量*区间长
		sum(p<<1|1)+=add(p)*(r(p<<1|1)-l(p<<1|1)+1); //区间和增量=数值增量*区间长
    add(p)=0;
  }
}

int query(int p,int l,int r) 
//更新后的区间查询，增加了下穿标记的操作
{
  if(l<=l(p) && r>=r(p)) return sum(p); //完全包含
  spread(p);//下传标记
  int mid=((l(p)+r(p))>>1);
  int ans=0;
  if(l<=mid) ans+=query(p<<1,l,mid);
  if(r>mid) ans+=query(p<<1|1,mid+1,r);
  return ans;
}

void update(int p int l,int r,int c)
{
  if(l<=l(p) && r>=r(p)){
		sum(p)+=c*(r(p)-l(p)+1); //区间和增量=数值增量*区间长
		add(p)+=c;
		return;
	}
	spread(p);//下传标记
	int mid=(l(p)+r(p))>>1;
	if(l<=mid) update(p<<1,l,r,c); //更新左子树
	if(r>mid) update(p<<1|1,l,r,c); //更新右子树
	sum(p)=sum(p<<1)+sum(p<<1|1); //更新当前点
}

复杂度为$O(logn)$

线段树

结构：

实现

操作

建树：

区间查询：

区间修改与延迟标记：

例题：