线段树——建树、更新、查询步骤解析（附习题）

ゝ一世哀愁。 2022-12-12 13:43 133阅读 0赞

> **①、什么是线段树？**  
> 答：线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。它能够实现很多功能，例如快速求区间和、求区间最大值、求区间最小值等。（在修改元素的基础上）  
> **②、为什么我们要用线段树？**  
> 答：使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。  
> 例如：  
> 有 N 个元素的数组。  
> 现在有两个操作：1、修改元素 2、求子区间和。  
> 思路一：  
> 假如我们用时间复杂度 O(1) 修改了元素 arr\[idx\] = val，那么查询区间和的时间复杂度将是 O(N)  
> 思路二：  
> 假如我们提前求出每个元素的前缀和并存储在sum数组中，那么查询区间 \[x, y\] 的方式为 sum\[y\] - sum\[x-1\] 时间复杂度为 O(1)，可是每修改一次 sum 数组都要更新时间复杂度又上升到 O(N)。  
> 思路三：  
> 利用线段树二分的思维，将查询与修改的操作都为时间复杂度 O(logN)。

本文步骤解析便实现一种功能——快速求出区间和

--------------------

[推荐学习视频][Link 1]

#### 线段树——建树 ####

为了更形象地将数组体现在线段树上，这里我将数组先初始化：

int arr[6] = { 1, 3, 5, 7, 9, 11};
    int tree[100]={ 0};

线段树的示意图  
![建树1][1]  
*ps : 黑色数字为每个节点的权值、红色数字为每个节点在数组 tree 的下标。*

通过观察树的结构可得  
①、每个叶子节点都是数组 arr 中的元素而且它们从左到右的顺序都是符合 arr 数组上的排序。  
②、除了叶子节点外，每个节点上的权值都等于它的左右节点上的权值和。  
③、除了叶子节点外，每个节点上的左右子节点的序号都能通过节点序号推导。例如节点的序号为 x，那么它的左子节点的序号为 2 \* x + 1，右子节点的序号为 2 \* x + 2。

到这里不难想到：**线段树是通过二分的方式建立的**。

为了更加直观，下面的红圈将树补齐为完全二叉树。  
![建树2][2]

--------------------

建树代码

//建树代码
    void bulid_tree(int node, int start, int end){ 
    	//到达叶子节点
    	if(start == end){ 
    		tree[node] = arr[start];
    	}
    	else{ 
    		int mid = (start + end) / 2;	//二分
    		int left_node  = 2 * node + 1;	//推导左子节点
    		int right_node = 2 * node + 2;
    		bulid_tree(left_node,  start, mid);	//递推
    		bulid_tree(right_node, mid+1, end);
    		//求得node节点的权值
    		tree[node] = tree[left_node] + tree[right_node];
    	}
    	return ;
    }

--------------------

#### 线段树——更新 ####

假如我们要改一个 arr 数组中的一个元素，那么我们只要更新根节点到对应元素的叶子节点的路径即可，不必再遍历其他节点，这也正是线段树的优势所在。

例如：当arr\[1\] = 3 ，修改为 arr\[1\] = 8。  
①、选择路径 0 --> 1 --> 3 --> 8  
![更新][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
②、修改路径上节点权值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

更新代码

void updata_tree(int node, int start, int end, int idx, int val){ 
       //找到对应叶子节点
       if(start == end){ 
       	arr[idx]   = val;
       	tree[node] = val;
       }
       else{ 
       	int mid = (start + end) / 2;
       	int left_node  = node * 2 + 1;
       	int right_node = node * 2 + 2;
       	
       	if(idx >= start && idx<=mid){ 
       		updata_tree(left_node,  start, mid, idx, val);
       	}
       	else{ 
       		updata_tree(right_node, mid+1, end, idx, val);
       	}
       	//更新路径上的节点
       	tree[node] = tree[left_node] + tree[right_node]; 
       }
    }

--------------------

#### 线段树——查询 ####

当我们查询 arr 数组区间 \[x, y\] 的和，我们**需要将线段树上对应区间节点相加**。

例如：查询 arr 数组上 \[2, 4\] 的区间和。  
①、寻找区间上对应的节点。  
![查询][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 2]  
②、将对应节点上的权值返回到上一级函数，最终返回到主函数的便是 \[3, 5\] 的区间。

优化：线段树的 2 号节点上的权值 27 恰好等于的是 \[3, 5\] 的区间和(7+9+11)。**我们大可不必一定要查询到叶子节点，若遍历的节点在所要查询的区间内，我们可以直接返回节点上的权值**。

--------------------

查询代码

int query_tree(int node, int start, int end, int L, int R){ 
    	if(R < start || L > end){ 
    		return 0;
    	}
    	else if((start >= L && end <= R)){ 
    		return tree[node];
    	}
    	else{ 
    		int mid = (start + end) / 2;
    		int left_node  = 2 * node + 1;
    		int right_node = 2 * node + 2;
    		
    		int sum_left  = query_tree(left_node,  start, mid, L, R);
    		int sum_right = query_tree(right_node, mid+1, end, L, R);
    		return sum_left + sum_right;
    	}
    }

--------------------

#### 整合代码 ####

#include<stdio.h>
    #define MAX_LEN 1000
    int arr[] = { 1, 3, 5, 7, 9, 11};
    int size = 6;
    int tree[MAX_LEN] = { 0};
    
    //建树
    void bulid_tree(int node, int start, int end){ 
    	if(start == end){ 
    		tree[node] = arr[start];
    	}
    	else{ 
    		int mid = (start + end) / 2;
    		int left_node  = 2 * node + 1;
    		int right_node = 2 * node + 2;
    		bulid_tree(left_node,  start, mid);
    		bulid_tree(right_node, mid+1, end);
    		tree[node] = tree[left_node] + tree[right_node];
    	}
    	return ;
    } 
    
    void updata_tree(int node, int start, int end, int idx, int val){ 
    	//出口 
    	if(start == end){ 
    		arr[idx]   = val;
    		tree[node] = val;
    	}
    	else{ 
    		int mid = (start + end) / 2;
    		int left_node  = node * 2 + 1;
    		int right_node = node * 2 + 2;
    		
    		if(idx >= start && idx<=mid){ 
    			updata_tree(left_node,  start, mid, idx, val);
    		}
    		else{ 
    			updata_tree(right_node, mid+1, end, idx, val);
    		}
    		//更新节点
    		tree[node] = tree[left_node] + tree[right_node]; 
    	}
    }
    
    int query_tree(int node, int start, int end, int L, int R){ 
    // printf("start = %d\n", start);
    // printf("end = %d\n", end);
    // printf("\n");
    	
    	if(R < start || L > end){ 
    		return 0;
    	}
    	else if(start >= L && end <= R){ 
    		return tree[node];
    	}
    	else{ 
    		int mid = (start + end) / 2;
    		int left_node  = 2 * node + 1;
    		int right_node = 2 * node + 2;
    		
    		int sum_left  = query_tree(left_node,  start, mid, L, R);
    		int sum_right = query_tree(right_node, mid+1, end, L, R);
    		return sum_left + sum_right;
    	}
    }
    
    int main(){ 
    	bulid_tree(0, 0, size-1);
    	for(int i = 0; i < 15; i++)
    		printf("tree[%d] = %d\n", i, tree[i]);
    	
    // printf("\n");
    	
    	updata_tree(0, 0, size-1, 4, 6);
    // for(int i = 0; i < 15; i++)
    // printf("tree[%d] = %d\n", i, tree[i]);
    	
    // printf("\n");
    	
    	int s = query_tree(0, 0, size-1, 2, 5);
    	printf("s = %d\n", s);
    	
    	return 0;
    }

--------------------

#### 习题 ####

巅峰对决 [题目链接][Link 2]  
![题目1][1 1]  
![题目2][2 1]

--------------------

##### 解题思路 #####

问题转换  
题目条件：数组内的元素始终不重复，判断指定区间 \[x, y\] 内的元素是否连续。  
解决方案：找出指定区间 \[x, y\] 中的最大值 max\_x 与最小值 min\_y。若 max\_x - min\_y == x - y 的话，则符合条件输出YES，否则输出NO。  
**问题转换为求指定区间 \[x, y\]中的最大值与最小值。**

--------------------

很明显，区间最大值与区间最小值的树是不同的。我们需要构造两个线段树，分别用于求区间最大值与区间最小值。

线段树操作  
①、建树  
区间最大值线段树与区间最小值线段树能够同时建树。  
那为什么能够同时建树呢？  
答：建树的过程是遍历一遍数组，区间最大值线段树与区间最小值线段树的对象数组是相同的，那么就能够同时建树。

void build_tree(int node, int start, int end){ 
    	if(start == end){ 
    		tree_min[node] = arr[start];
    		tree_max[node] = arr[start];
    		return;
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = 2 * node + 1;
    	int right_node = 2 * node + 2;
    	build_tree(left_node , start, mid);
    	build_tree(right_node, mid+1, end);
    	tree_min[node] = min(tree_min[left_node], tree_min[right_node]);
    	tree_max[node] = max(tree_max[left_node], tree_max[right_node]);
    }

②、更新  
同理因为区间最大值线段树与区间最小值线段树的对象数组都是相同的那么能够实现同时更新。

void updata_tree(int node, int start, int end, int idx, int val){ 
    	if(end<idx || start>idx){ 
    		return;
    	}
    	if(start == end){ 
    		if(start == idx){ 
    			tree_min[node] = val;
    			tree_max[node] = val;
    			arr[idx] = val;
    		}
    		return ;
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = 2 * node + 1;
    	int right_node = 2 * node + 2;
    	updata_tree(left_node , start, mid, idx, val);
    	updata_tree(right_node, mid+1, end, idx, val);
    	tree_min[node] = min(tree_min[left_node], tree_min[right_node]);
    	tree_max[node] = max(tree_max[left_node], tree_max[right_node]);
    }

③、查询  
最大值线段树与区间最小值线段树在进行查询操作时要分开进行。  
为什么查询就要分开进行呢？  
答：因为两棵线段树的作用不同，所以它们查询的方式也会不同。

//查询区间最大值
    int query_max(int node, int start, int end, int L, int R){ 
    	if(start>=L && end<=R){ 
    		return tree_max[node];
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = node * 2 + 1;
    	int right_node = node * 2 + 2;
    
    	//缩小查询范围
    	if(mid >= R){ 
    		return query_max(left_node , start, mid, L, R);
    	}
    	else if(mid < L){ 
    		return query_max(right_node, mid+1, end, L, R);
    	}
    	
    	return max(query_max(left_node , start, mid, L, R), query_max(right_node, mid+1, end, L, R));
    }
    
    //查询区间最小值
    int query_min(int node, int start, int end, int L, int R){ 
    	if(start>=L && end<=R){ 
    		return tree_min[node];
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = node * 2 + 1;
    	int right_node = node * 2 + 2;
    	if(mid >= R){ 
    		return query_min(left_node , start, mid, L, R);
    	}
    	else if(mid < L){ 
    		return query_min(right_node, mid+1, end, L, R);
    	}
    	
    	return min(query_min(left_node , start, mid, L, R), query_min(right_node, mid+1, end, L, R));
    }

--------------------

实现代码

#include<bits/stdc++.h>
    using namespace std;
    int tree_min[400010], tree_max[400010];
    int arr[100010];
    
    void build_tree(int node, int start, int end){ 
    	if(start == end){ 
    		tree_min[node] = arr[start];
    		tree_max[node] = arr[start];
    		return;
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = 2 * node + 1;
    	int right_node = 2 * node + 2;
    	build_tree(left_node , start, mid);
    	build_tree(right_node, mid+1, end);
    	tree_min[node] = min(tree_min[left_node], tree_min[right_node]);
    	tree_max[node] = max(tree_max[left_node], tree_max[right_node]);
    }
    
    void updata_tree(int node, int start, int end, int idx, int val){ 
    	if(end<idx || start>idx){ 
    		return;
    	}
    	if(start == end){ 
    		if(start == idx){ 
    			tree_min[node] = val;
    			tree_max[node] = val;
    			arr[idx] = val;
    		}
    		return ;
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = 2 * node + 1;
    	int right_node = 2 * node + 2;
    	updata_tree(left_node , start, mid, idx, val);
    	updata_tree(right_node, mid+1, end, idx, val);
    	tree_min[node] = min(tree_min[left_node], tree_min[right_node]);
    	tree_max[node] = max(tree_max[left_node], tree_max[right_node]);
    }
    
    int query_max(int node, int start, int end, int L, int R){ 
    	if(start>=L && end<=R){ 
    		return tree_max[node];
    	}
    	if(end<L || start>R){ 
    		return 0;
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = node * 2 + 1;
    	int right_node = node * 2 + 2;
    	if(mid >= R){ 
    		return query_max(left_node , start, mid, L, R);
    	}
    	else if(mid < L){ 
    		return query_max(right_node, mid+1, end, L, R);
    	}
    	
    	return max(query_max(left_node , start, mid, L, R), query_max(right_node, mid+1, end, L, R));
    }
    
    int query_min(int node, int start, int end, int L, int R){ 
    	if(start>=L && end<=R){ 
    		return tree_min[node];
    	}
    	
    	int mid = (start+end) / 2;
    	int left_node  = node * 2 + 1;
    	int right_node = node * 2 + 2;
    	if(mid >= R){ 
    		return query_min(left_node , start, mid, L, R);
    	}
    	else if(mid < L){ 
    		return query_min(right_node, mid+1, end, L, R);
    	}
    	
    	return min(query_min(left_node , start, mid, L, R), query_min(right_node, mid+1, end, L, R));
    }
    
    int main(){ 
    	int n, q;
    	scanf("%d%d", &n, &q);
    	for(int i=0; i<n; i++)
    		scanf("%d", &arr[i]);
    	build_tree(0, 0, n-1);
    	int op, x, y;
    	while(q--){ 
    		scanf("%d%d%d", &op, &x, &y);
    		if(op==1){ 
    			updata_tree(0, 0, n-1, x-1, y);
    		}
    		else{ 
    			int ans1 = query_min(0, 0, n-1, x-1, y-1);
    			int ans2 = query_max(0, 0, n-1, x-1, y-1);
    			int ans = ans2 - ans1;
    			if(ans == y-x){ 
    				printf("YES\n");
    			}
    			else{ 
    				printf("NO\n");
    			}
    		}
    	}
    	return 0;
    }

--------------------

#### 总结 ####

线段树一般作用需要多次查询操作的在较大的数组上。  
它能够大大降低时间复杂度，值得好好深究。

[Link 1]: https://b23.tv/UJDqF4
[1]: /images/20221123/dcd841e196a14c2aaeb52e2355da911c.png
[2]: /images/20221123/7909f0c024da4ffb9ae9ae2498ad7d0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/2738aefbe9b540f0aa64ce6062ed3ae0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/674beb4ff12e4e11aac7f4fc2639689a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/d828dcd09146427184db0af4ce6d2647.png
[Link 2]: https://ac.nowcoder.com/acm/contest/6874/D
[1 1]: /images/20221123/c343c4215b344b05b4c059a3d9ee2254.png
[2 1]: /images/20221123/691f84527de140fdbcfad92733bf9db5.png