线段树（周家宝）

[TUStarry]

线段树

基本信息

全称

线段树（Segment Tree）

起源与介绍

线段树是一种二叉树，可视为树状数组的变种，最早出现在2001年，由竞赛选手发明。

作用

此数据结构实际应用用途不大，但由于其程式易于实作而被广泛应用于程式竞赛当中。其用途是在O（logN）查询一个指定区间内的资讯，并可在同样的时间复杂度支援更新等操作。

基本概念

线段树是一种基于分治思想的二叉树，用于在区间上进行信息的统计。与按照二进制进行区间划分的树状数组相比，线段树是一种更加通用的结构；

1. 线段树的每一个节点都代表一个区间
2. 线段树具有的唯一根节点，代表的区间是整个统计范围，[1，n]
3. 线段树的每个叶节点都代表长度为1的元区见[x，x]
4. 对于每个内部节点[l，r]，它的左节点是[l, mid]，右节点是[mid, r]，其中mid = (l + r) / 2(向下取整)

区间试图：

二叉树视角：

线段树建树

首先用struct数组来存储线段树，代码如下：

struct SegmentTree{
	int left, right;
	int data;
}t[SIZE * 4]; //struct数组存储线段树 

1提问：欸，学长学长，这里为甚么是size * 4

• 在理想的情况下，N个叶节点的满二叉树有 N + N/2 + N/4 + ……+ 2 + 1 = 2N - 1个节点，但这是理想的情况下；按照上面的二叉树视角下，共有节点2N - 1 个节点，但是在【6，7】处的节点编号为12，它的左右子节点的编号分别是24，25，大2N - 1；如果你定义的数组大小是2N的话，那么你就会裂开；
• 在上述描述的存储方式下，最后一层会有空余，按照二叉树子节点为父节点编号2倍的情况下，2 * （2N - 1）的大小无疑是最保险的

接下来开始建线段树：

void build(int point,int left, int right){
	t[point].left = left, t[point].right = right; //节点p代表区间【left，right】 
	if (left == right){					  //叶节点 
		t[point].data = arr[l]; 		  //arr数组是原始数据
		return;
	}
	int mid = (left + right) / 2;		  //折半 
	build(point*2, left, mid);			  //左子节点【left，mid】，编号p*2 
	build(point*2+1, mid+1, right);		  // 右子节点【mid，right】，编号p*2+1 
	/*
	按照题目要求，其它的操作
	以区间最大值为例子
	t[point].data = max(t[point*2].data, t[point*2 + 1].data); //从下往上传递信息
	*/
    
} 


build(1, 1, n); 						  //调用入口

2提问：欸，学长学长，我没有问题，你有没有什么想告诉我的

• 线段树的基本用途是对序列进行维护，支持查询与修改指令。给定一个长度为N的序列arr，我们可以在区间【1，N】上建立一颗线段树，每个节点【i，i】保存arr【i】的值；线段树的二叉树结构可以很方便的从下往上传递信息。

线段树的单点修改

不用假设，我现在非常的闲，于是我准备修改数组arr【x】的值为val，于是线段树的某些值也就发生了变化；可以简单的想到单点修改的时间复杂度为O（logN）。

void change(int point, int x, int val){
	if (t[point].left == t[point].right){//找到叶节点 
		t[point].data = val;
		return;
	}
	int mid = (t[point].left + t[point].right) / 2; //熟悉的二分 
	if (x <= mid)
		change(point*2, x, val); 	//x在左边 
	else
		change(point*2+1, x, val); //x在右边 
	/*
	按照题目要去，其它的操作
	以区间最大值为例子
	t[point].data = max(t[point*2].data, t[point*2 + 1].data); //从下往上传递信息
	*/ 
} 

change(1, x ,val);		//调用入口 

3提问：欸，学长学长，你有什么想说的吗

• 没

线段树的区间查询

还是不用假设，我就是闲，现在想查询序列arr在区间【left，right】上的最大值；我们需要从根节点开始，递归执行以下的过程：

1. 若【left，right】完全覆盖了当前节点代表的区间，则立即回溯，并且该节点的data作为候选答案
2. 若左子节点与【left，right】有重叠的部分，则递归访问左子节点
3. 若右子节点与【left，right】有重叠的部分，则递归访问右子节点

int ask(int point,int left, int right){
	if ( <= t[point] && t[point].right <= right) //【left，right】完全覆盖了当前节点代表的区间
		return t[point].data;
	int mid = (t[point].left + t[point].right) / 2; //熟悉的二分
	int val =-(1 << 30);  //负无穷大
	if (left <= mid)
		val = max(val, ask(point*2, left, right)); //左子节点与【left，right】有重叠的部分，则递归访问左子节点
	if (mid < right)
		val = max(val, ask(point*2+1, left, right)); //右子节点与【left，right】有重叠的部分，则递归访问右子节点
	return val;
}

printf("%d\n",ask(1, left, right));//在【left，right】区间的最大值

时间复杂度的问题

• 线段树的区间查询是一个O（logN）的操作，每一次递归都会让他少一半的查询空间

线段树的懒标记（进阶）

接下来我们引入一道题目来进行进阶

线段树（模板1）：（https://www.luogu.com.cn/problem/P3372）

• 首先用struct数组来存储线段树

struct SegmentTree{
	int left, right;
	int data, lazy; //新加入lazy标签
}t[SIZE * 4]; 

• 建树

void build(int point,int left, int right){
	t[point].left  = left;
	t[point].right = right;
	if(left == right){
		t[point].data = arr[left];
		return; 
	}
	int mid = (left + right) / 2;
	build(point*2, left, mid);
	build(point*2+1, mid, right);
	t[point].data = t[point*2].data + t[point*2+1].data;
}

• 懒标记

懒标记是一个神奇的东西，为什么叫懒标记，因为它比较懒 懒标记的精髓就是打标记和下传操作，由于我们要做的操作是区间加一个数，所以我们不妨在区间进行修改时为该区间打上一个标记，就不必再修改他的儿子所维护区间，等到要使用该节点的儿子节点维护的值时，再将懒标记下放即可，可以节省很多时间，对于每次区间修改和查询，将懒标记下传，可以节省很多时间

void lazytag(int point){
    if(t[point].lazy){//如果懒标记不为0，就将其下传，修改左右儿子维护的值
        t[point*2].data += t[point].lazy*(t[point*2].right-t[point*2].left+1);
        t[point*2+1].data += t[point].lazy*(t[point*2+1].right-t[point*2+1].left+1);
        t[point*2].lazy += t[point].lazy;//为该节点的左右儿子打上标记
        t[point*2+1].lazy += t[point].lazy;
        t[point].lazy = 0;//下传之后将该节点的懒标记清0
    }
}

• 区间修改

void change(int point, int x, int y, int val){
	if (x <= t[point].left && t[point].right <= y){
		t[point].data += (ll)val * (t[point].right-t[point].left+1);
        t[point].lazy += val;//打上懒标记
        return;
	}
	lazytag(point);//如果发现没有被覆盖，那就需要继续向下找，考虑儿子所维护的区间可能因为懒标记的存在而没有修改，因此将懒标记下放
	int mid = (t[point].left + t[point].right) / 2; //熟悉的二分 
	if (x <= mid)
		change(point*2, x, y, val); 	//x在左边 
	if (mid < y)
		change(point*2+1, x, y, val); //x在右边 
	t[point].data = t[point*2].data + t[point*2+1].data;
} 

• 区间查询

ll ask(int point, int x, int y){
	if(x <= t[point].left && t[point].right <= y)
		return t[point].data;
	lazytag(point);//下传懒标记，并查询左右儿子
	int mid = (t[point].left + t[point].right) / 2; //熟悉的二分
	ll val = 0;  
	if (x <= mid)
		val += ask(point*2, x, y);
	if(mid < y)
		val += ask(point*2+1, x, y);
	return val;
}

• 最后

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int SIZE = 100010;
struct SegmentTree{
	int left, right;
	ll data, lazy;
}t[SIZE * 4]; //struct数组存储线段树 
int arr[SIZE];

void build(int point,int left, int right){
	t[point].left  = left, t[point].right = right;
	if(left == right){
		t[point].data = arr[left];
		return; 
	}
	int mid = (left + right) / 2;
	build(point*2, left, mid);
	build(point*2+1, mid+1, right);
	t[point].data = t[point*2].data + t[point*2+1].data;
}
void lazytag(int point){
    if(t[point].lazy){//如果懒标记不为0，就将其下传，修改左右儿子维护的值
        t[point*2].data += t[point].lazy*(t[point*2].right-t[point*2].left+1);
        t[point*2+1].data += t[point].lazy*(t[point*2+1].right-t[point*2+1].left+1);
        t[point*2].lazy += t[point].lazy;//为该节点的左右儿子打上标记
        t[point*2+1].lazy += t[point].lazy;
        t[point].lazy = 0;//下传之后将该节点的懒标记清0
    }
}

void change(int point, int x, int y, int val){
	if (x <= t[point].left && t[point].right <= y){
		t[point].data += (ll)val * (t[point].right-t[point].left+1);
        t[point].lazy += val;//打上懒标记
        return;
	}
	lazytag(point);//如果发现没有被覆盖，那就需要继续向下找，考虑儿子所维护的区间可能因为懒标记的存在而没有修改，因此将懒标记下放
	int mid = (t[point].left + t[point].right) / 2; //熟悉的二分 
	if (x <= mid)
		change(point*2, x, y, val); 	//x在左边 
	if (mid < y)
		change(point*2+1, x, y, val); //x在右边 
	t[point].data = t[point*2].data + t[point*2+1].data;
} 



ll ask(int point, int x, int y){
	if(x <= t[point].left && t[point].right <= y)
		return t[point].data;
	lazytag(point);//下传懒标记，并查询左右儿子
	int mid = (t[point].left + t[point].right) / 2; //熟悉的二分
	ll val = 0;  
	if (x <= mid)
		val += ask(point*2, x, y);
	if(mid < y)
		val += ask(point*2+1, x, y);
	return val;
}
int main(){
	int n, m;
	scanf("%d%d",&n, &m);
	for(int i=1;i<=n;i++)
		scanf("%d",&arr[i]);
	build(1,1,n);
	while(m--){
		int ch, x, y, k;
		scanf("%d",&ch);
		if (ch == 1){
			scanf("%d%d%d",&x, &y, &k);
			change(1,x,y,k); 
		}
		else{
			scanf("%d%d",&x, &y);
			printf("%lld\n", ask(1,x,y));
		}		
	}
	return 0;
}

参考资料：（线段树圣经）