线段树杂谈

概念：

线段树（Segment Tree）是一个基于分治的数据结构。

通常处理区间，序列中的查询，更改问题。大体上有单修，单查，区修，区查等操作。但因为其可维护变量的多样性，所以常在各类题目中遇到。准确说，是各类优化中遇到。

线段树是个有根二叉树，我们记为 t，其每个节点 t[p] 均保存着所应该记录的关键信息（依题目情况而定）。对于每一个区间，我一般不喜欢在结构体里记录它的区间端点信息，一般在函数递归中开两个参数进行处理。

实现1（单点修改，区间查询）：

首先我们有这样一个序列a：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

我们希望对其中下标为 $i$ 的元素进行修改，并且能够快速查找区间 $l$ 到 $r$ 中的最大值。

Step 1，建树：

struct node{
	int mx;
}tree[MAXN];//记录每个节点里的关键信息，这里记录了节点区间里的最大值
void build(int i,int tl,int tr){//递归建树，i表示节点编号，tl，tr表示该节点所含的区间（后同）
	if(tl == tr){
		tree[i].mx = a[tl];
		return;
	}
	int mid = (tl + tr) / 2;
	build(i << 1,tl,mid);//进行递归建树操作，分别建左子树和右子树
	build((i << 1) + 1,mid + 1,tr);
	tree[i].mx = max(tree[i<<1].mx,tree[(i<<1) + 1].mx);//子树建完后，进行上传操作，更新该区间tree[i]的最大值（意会一下）
}

Step 2，单点修改：

void change(int i,int tl,int tr,int pos,int num){//pos为要修改的下标，num为修改后的值
	if(tl == tr){//已到达要修改的下标
		tree[i].mx = num;
		return;
	}
	int mid = (tl + tr) / 2;
	if(pos <= mid){//如果包含在左子树里，那么就在该子树里进行递归直到到达目标节点
		change(i<<1,tl,mid,pos,num);
	}
	else{//被包含在右子树里
		change((i<<1) + 1,mid + 1,tr,pos,num);
	}
	tree[i].mx = max(tree[i<<1].mx,tree[(i<<1) + 1].mx);//修改完值后，自然要更新区间包含这个下标的树上的节点
}

Step 3，区间查询：

查询 $l$ 到 $r$ 这一区间里的最大值。

int query(int i,int tl,int tr,int l,int r){
	if(l > r)return -MAXN;//区间越界，返回最小值
	if(tl == l && tr == r){
		return tree[i].mx;
	}
	int mid = (tl + tr) / 2;//如果查询的区间被左右子树各包含一点，那么将这个查询的区间分为落在左子树里的区间和落在右子树里的区间，对分后的两个区间所返回的最大值取一次最大值
	return max(query(i<<1,tl,mid,l,min(r,mid)),query((i<<1) + 1,mid + 1,tr,max(l,mid + 1),r));
}

单点修改，区间查询的方法就介绍到这里了。

实现2（区间修改，单点/区间查询）：

如果说单点修改，区间查询的实现中最重要的就是数据的上传操作，那么我觉得区间修改，单点/区间查询最重要的就是数据的下传操作。

什么是下传操作？我们通过对下面这道题的分析来进行理解。

有一列长度为 $n$ 的路灯，每一次操作下标 $l$ 到 $r$ 的路灯的开关，使得每个路灯的状态发生改变（亮变灭 $or$ 灭变亮）。所有灯初始时都是灭的，经过 $m$ 次操作后，有 $x$ 次查询，每一次查询操作给出 $l$ $r$ 两个下标，查询 $l$ 到 $r$ 中有多少盏路灯是亮着的。

在这道题目中，对于修改操作中的 $l$ $r$，如果我们将这个区间里面每个路灯的状态逐一进行改变，时间复杂度肯定是不会令人满意的。但是我们可以对每个节点设置一个标记 $sta$，$1$ 表示该节点所表示的区间内的所有灯都是亮着的，$0$ 表示所有灯都是灭的，$-1$ 表示该区间里既有灭的，又有亮的。

在这个题里，因为所有灯初始为灭的，且 $sta$ 的默认值为 $0$，我们就可以取消建树操作。

Step 1，区间修改：

void change(int i,int tl,int tr,int l,int r){//所有字母含义均一样，不同的是，在区修的过程中，我们不必改变l和r的值，我们可以让我们处理的区间范围来“适应”修改的区间范围，建议结合代码理解
	if(tl > r || tr < l)return;//如果当前节点的区间跟修改区间毫不相交，那么就没有递归处理的必要了，直接返回，这就是“适应”操作
	if(tl >= l && tr <= r){//假如当前节点的区间被完全包含在修改的区间里面，那么直接整体修改区间的值并返回，不必继续递归（虽然该节点以下的所有子树的信息并没有得到修改）
		tree[i].sta = !tree[i].sta;
		return;
	}
	if(tree[i].sta != -1){
		tree[i<<1].sta = tree[(i<<1) + 1].sta = tree[i].sta;//注意，这里就是数据的下传操作，因为该区间在修改后就会既有亮的又有灭的，而之前在进行整体操作时并没有对子树进行修改，所以在修改前就应该把当前节点的纸更新到左儿子和右儿子上
	}
	tree[i].sta = -1;
	int mid = (tl + tr) / 2;
	chaneg(i<<1,tl,mid,l,r);
	change((i<<1) + 1,mid + 1,tr,l,r);
}

Step 2，区间查询：