数据结构之线段树从入门到进阶附代码模板

偏执的太偏执、 2023-03-04 09:24 74阅读 0赞

#### 一、线段树入门 ####

[线段树][Link 1]是啥，简单来说就是既方便我们求一个数组某区间的和，又方便我们修改数组的某个元素的一种数据结构。属于二叉搜索树。

对于一个普通数组来说，我们修改某一元素的时间复杂度是O(1)，但求某区间和的时间复杂度是O(n)。  
若使用[前缀和][Link 2]，我们求某区间和的复杂度是O(1)，但我们修改某一元素的复杂度是O(n)。

为了方便我们又修改又求和，我们就使用线段树来均衡这两个操作的复杂度，把他们都平均到O(logn)。

#### 具体操作 ####

我们通常用一个数组来模拟一棵满二叉树，该二叉树的根结点保存的是数组0-n所有元素的和，而根结点的左儿子保存的是0 ~ mid（mid是n/2，就是数组的左边一半）的所有元素和，根结点的右儿子保存的是mid+1 ~ n（mid同上，这里就是数组的右一半）的所有元素和，每个结点都如此一直到叶节点保存的是数组的一个元素。就相当于每层都把其劈成两半，左儿子保存左边的一半和，右儿子保存右边的一半和。

线段树的主要操作有修改元素，求区间和。主要的函数还有一个建树函数。  
这里主要实现了单点修改与区间求和。

基本函数都用递归的思想，具体解释见代码。

#### 代码模板及详解 ####

#include<iostream>
    using namespace std;
    const int N = 1010;
    
    int arr[6] = { 1,3,5,7,9,11},tree[N];	//直接默认指定数组arr，tree是模拟线段树的数组
    
    void build(int node,int start,int end)	//建树，node是当前结点编号，start是开始的数组元素编号，end是结束的数组元素编号
    { 
    	if(start == end)	//递归推出的条件，开始和结束的元素相等，说明到了叶结点
    		tree[node] = arr[start];	//赋值，tree的当前结点node的值是arr数组的start元素
    	else
    	{ 
    		int mid = (start + end) / 2;	//中点
    		int left = node * 2 + 1;	//左儿子的下标
    		int right = node * 2 + 2;	//右儿子的下标
    		build(left,start,mid);		//递归左边，当前结点递归到左儿子，元素从start到mid
    		build(right,mid+1,end);		//递归右边，当前结点递归到右儿子，元素从mid+1到end
    		tree[node] = tree[left] + tree[right];	//tree的当前结点是左儿子和右儿子的和
    	}
    }
    
    void update(int node,int start,int end,int idx,int val)	//修改操作
    { 
    	if(start == end)	//递归退出的条件，如果start和end重合，说明找到了该叶结点
    	{ 
    		arr[idx] = val;	//修改原数组
    		tree[node] = val;	//修改树的叶结点
    	}
    	else
    	{ 
    		int mid = (start + end) / 2;	//中点
    		int left = node * 2 + 1;	//左儿子的下标
    		int right = node * 2 + 2;	//右儿子的下标
    		if(idx > mid)	//如果下标大于中点，说明在右儿子分支，往右递归搜索
    			update(right,mid+1,end,idx,val);
    		else		//else 往左递归
    			update(left,start,mid,idx,val);
    		tree[node] = tree[left] + tree[right];	//上面递归找到后，要修改到根结点路径上的值
    	}
    }
    
    int query(int node,int start,int end,int l,int r)	//求区间和操作，从l到r区间的和
    { 
    	if(l > end || r < start)	//递归的出口1，当前区间不在所求区间内，返回0
    		return 0;
    	else if(start == end || (start > l && end < r))	//递归出口2，start == end说明到叶结点了，当前线段树区间在所求区间内部，就不用再分了，返回当前结点的值
    		return tree[node];
    	int mid = (start + end) / 2;
    	int left = node * 2 + 1;
    	int right = node * 2 + 2;
    	int suml = query(left,start,mid,l,r);	//递归左儿子
    	int sumr = query(right,mid+1,end,l,r);	//递归右儿子
    	return suml + sumr;	//返回左儿子和右儿子的和
    }
    	
    int main()
    { 
    	build(0,0,5);	//建树，当前结点是0（根结点），从数组0到5，即所有元素
    	for(int i = 0;i < 15;i++)
    		cout << tree[i] << " ";
    	cout << endl;
    
    	update(0,0,5,4,6);	//修改下标为4的元素为6
    	for(int i = 0;i < 15;i++)
    		cout << tree[i] << " ";
    	cout << endl;
    
    	int sum = query(0,0,5,2,5);	//计算区间2到5的区间和
    	cout << sum << endl;
    	
    	return 0;
    }

#### 二、线段树的进阶 ####

这里主要实现了区间修改及单点查询

这里主要用pushdown函数实现懒标记，若要对某一区间进行修改（都+k），我们一个一个循环单点修改复杂度太高，太麻烦，这里我们用一个懒标记（lazytarget）用lz数组代替。当我们搜索到当前区间在目标区间内部时，我们给该区间加上（end-start+1）\* k，并标记该区间（lz= k），下次若查询该区间内的某值时，只需加上长度\*k即可。

具体见代码：

#### 代码解析 ####

#include<iostream>
    using namespace std;
    const int N = 1010;
    
    int arr[4] = { 1,2,3,4},tree[N],lz[N];
    
    void build(int node,int start,int end)	//和上面的建树函数一样
    { 
    	if(start == end)
    	{ 
    		tree[node] = arr[start];
    		return;
    	}
    	else
    	{ 
    		int mid = (start + end) / 2;
    		int left = node * 2 + 1;
    		int right = node * 2 + 2;
    		build(left,start,mid);
    		build(right,mid+1,end);
    		tree[node] = tree[left] + tree[right];
    	}
    }
    
    void pushdown(int node,int start,int end)	//pushdown函数，检查懒标记的
    { 
    	if(!lz[node])	//如果该结点有懒标记
    	{ 
    		int mid = (start + end) / 2;
    		int left = node * 2 + 1;
    		int right = node * 2 + 2;
    		lz[left] += lz[node];	//左右儿子继承懒标记
    		lz[right] += lz[node];
    		tree[left] += lz[left] * (mid-start+1);	//左右儿子加上长度*懒标记
    		tree[right] += lz[right] * (end-mid);
    		lz[node] = 0;
    	}
    }
    
    void update(int node,int start,int end,int l,int r,int k)	//给l到r区间加k
    { 
    	if(start >= l && end <= r)	//如果当前区间在目标区间内
    	{ 
    		tree[node] += (end - start + 1) * k;	//当前结点加上长度*k
    		lz[node] = k;	//懒标记+k
    		return;
    	}
    	pushdown(node,start,end);	//向下传懒标记
    	int mid = (start + end) / 2;
    	int left = node * 2 + 1;
    	int right = node * 2 + 2;
    	if(mid+1 <= r)	//如果右儿子起点小于等于目标右端点，向右搜索
    		update(right,mid+1,end,l,r,k);
    	if(mid >= l)	//同理，左儿子右端点大于等于目标左端点，向左搜索
    		update(left,start,mid,l,r,k);
    	tree[node] = tree[left] + tree[right];	//更新该结点
    }
    
    int query(int node,int start,int end,int l,int r)	//查询区间和或单点值
    { 
    	if(start >= l && end <= r)	//若当前区间在目标区间内
    		return tree[node];	//返回当前结点值
    	if(start > r || end < l)	//如果不在目标区间内，返回0
    		return 0;
    	int mid = (start + end) / 2;
    	int left = node * 2 + 1;
    	int right = node * 2 + 2;
    	pushdown(node,start,end);	//向下传懒标记
    	int suml = query(left,start,mid,l,r);	//左边求和递归
    	int sumr = query(right,mid+1,end,l,r);	//右边求和递归
    	return suml + sumr;	//返回左右之和
    }
    
    int main()
    { 
    	build(0,0,3);	//测试数据
     
    	update(0,0,3,0,2,1);
    	for(int i = 0;i < 7;i++)
    		cout << tree[i]<<" ";
    	cout << endl;
    	
    	int sum = query(0,0,3,1,2);
    	cout << sum;
    
    	return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E7%BA%BF%E6%AE%B5%E6%A0%91
[Link 2]: https://blog.csdn.net/qq_45735851/article/details/106535635