线段树随笔

发布时间:2024年01月05日

线段树

题外话

这是一篇随笔,仅做记录用,里面不会讲解思想之类的,看到这如果是为了学习线段树之类的可以跳过了。

下面如果有讲错的敬请斧正,我也第一天学。

线段树用于处理一维数组的“区间和”问题,比如有一个N个数的一维数组,你在这个数组的元素上加加减减M次,比如在[1,5]上加1000,[2,10000]加1(这里的区间都是指的是下标,加1指的是让数组这个区间上的元素加1),然后让你求特定区间的区间和,数据量小暴力就行,数据大复杂度就起来了——O(N*M),而如果使用线段树,复杂度就是(M*logN),这是一个巨大的优化。

代码

思想和下面这个up主学的,代码看了他之后自己敲的,遇到的问题进行了记录。

传送门在这👈

代码就在下面,我遇到的问题也写了注释,有问题可以评论问我,会的话会回的。

#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;

#define MAXN 1000

//建树
void build_tree(int arr[], int tree[], int node, int start, int end)//建立node和左右孩子的关系,start和end是arr的下标
{
	if (start == end)//比如区间为(3,3)就停止建树
	{
		tree[node] = arr[start];//叶子结点赋值,因为上一层的递归需要计算tree[node],需要左右孩子的值
		return;
	}
	int mid = (start + end) / 2;//区间中点,比如[0,5],mid就是2,由此分为[0,2] [3,5]
	int left_node = 2 * node + 1;//左孩子(类似堆)
	int right_node = 2 * node + 2;//右孩子(类似堆)
	
	build_tree(arr, tree, left_node, start, mid);//递归建立左孩子与其自己孩子的关系
	build_tree(arr, tree, right_node, mid+1, end);//递归建立右孩子与自己孩子的关系

	tree[node] = tree[left_node] + tree[right_node];//计算当前结点的值
}
void update_tree(int arr[], int tree[], int node, int start, int end, int index, int val)//更新arr index位置的val
{
	if (start == end)//只有一个数说明找到了
	{
		arr[index] = val;//修改数组这个位置的值
		tree[node] = val;//修改tree这个结点的值
		return;
	}

	int mid = (start + end) / 2;//区间中点,比如[0,5],mid就是2,由此分为[0,2] [3,5]
	int left_node = 2 * node + 1;//左孩子
	int right_node = 2 * node + 2;//右孩子

	//index在这之间就下去找到它(下面其实就是二分的递归)
	if (index >= start && index <= mid)
	{
		update_tree(arr, tree, left_node, start, mid, index, val);
	}
	else if (index >= mid + 1 && index <= end)
	{
		update_tree(arr, tree, right_node, mid+1, end, index, val);
	}
	else//区间内没有这个index,直接return
	{
		return;
	}
	tree[node] = tree[left_node] + tree[right_node];//上面找到了对应的数,即孩子已经更新,更新一下父亲
}

//算区间[L,R]的值
int query(int arr[], int tree[], int node, int start, int end,int L, int R)
{

	if (R<start || L>end)
	{
		return 0;
	}
	else if (start>=L&&end<=R)//记这里为优化A(最关键的优化,把O(n)优化成了O(logn)
	{
		//判断条件的意思是假如[start,end]在[L,R]里面,直接返回表示这个区间的值即可
		return tree[node];
		//我当时有一个疑问,比如[2,5]是所求区间,且[2,5]=[2]+[3,5];[3,5]是某个结点表示的区间,直接返回[3,5]的值优化计算没有问题
		//问题在于那剩下的[2]是怎么算出来的,我明明没有处理[2]结果为什么是对的?
		//其实已经处理了,我们计算sum是用左子树+右子树,即一开始[2,5]里的[2]就被分到了[0,2]这棵树进行运算
	}
	else if (start == end)//去掉优化A,用这里的代码计算其实就是遍历到叶子再返回,也就是O(n)
	{
		return tree[node];
	}
	else
	{
		int mid = (start + end) / 2;//区间中点,比如[0,5],mid就是2,由此分为[0,2] [3,5]
		int left_node = 2 * node + 1;//左孩子
		int right_node = 2 * node + 2;//右孩子
		int sum_left = query(arr, tree, left_node, start, mid, L, R);
		int sum_right = query(arr, tree, right_node, mid+1, end, L, R);
		return sum_left + sum_right;

	}


}


int main()
{
	int arr[] = { 1,3,5,7,9,11 };
	int sz = sizeof(arr) / sizeof(int);
	int tree[MAXN] = { 0 };
	build_tree(arr, tree, 0, 0, sz - 1);//建线段树
	update_tree(arr, tree, 0, 0, sz - 1, 4, 6);//测试把arr[4]改成6,同时更新线段树
	cout<<query(arr, tree, 0, 0, sz - 1, 2, 5)<<endl;//测试[2,5]的和
	for (int i = 0; i < 15; i++)
	{
		cout << tree[i] << " ";
	}

	return 0;
}

文章来源:https://blog.csdn.net/m0_53005929/article/details/135414817
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。