线段树随笔

线段树

题外话

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

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

线段树用于处理一维数组的“区间和”问题，比如有一个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;
}