【C++】线段树（一）

 【引入】

【问题】

 一个有n个数的序列，进行q次提问：第x到第y个数字（包括x，y）的总和。

在没学线段树之前，我们首先想到的肯定是遍历第x到第y个数，再把它们的和相加。

就像这样：

#include<bits/stdc++.h>
using namespace std;
int num[1000000],n,q,x,y;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>num[i];
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		long long ans=0;
		for(int j=x;j<=y;j++)ans+=num[j];
		cout<<ans<<endl;
	}
}

但n,q大于一定范围就会超时。所以就要用到线段树。

【概念】

线段树其实是一种树形数据结构。回到刚才的问题，如果有一种结构能贮存所有x到y的和，当问的时候直接调用就好了。于是我就想到了二叉树，比如一个{1,2,3,4,5,6,7,8,9}的序列根节点用来储存1~9左子树右子树分别贮存1~5和5~9，以此类推（如下图）。

                1~9SUM:45
                 /       \
                /         \
          1~5SUM:15        6~9SUM:30
            /   \             /     \
           /     \           /       \
     1~3SUM:6   4~5SUM:9  6~7SUM:13  8~9SUM:17
        /  \       /  \      /  \       /   \
       /    \     /    \    /    \     /     \
  1~2SUM:3   3   4      5  6      7   8       9
     /  \
    /    \
   1      2
      

【建树(build)】

我们用一维数组来储存这棵二叉树，观察上图不难发现：如果父节点为k那么左节点2k

右子节点为2k+1，所以在最坏情况下一维数组的大小是序列的4倍。用递归建树。

/*SUM是用于存贮二叉树的一维数组，num是序列*/
void Build(int l,int r,int k)
{
    if(l==r){SUM[k]=num[l];return;}//边界条件
    int mid=(l+r)/2;
    Build(l,mid,2*k);//建立右子树
    Build(mid+1,r,2*k+1);//建立左子树
    SUM[k]=SUM[2*k]+SUM[2*k+1];
}

【查找(find)】

树建完了，那要如何访问呢？用递归遍历树，返回总和。

int Find(int l,int r,int k,int ll,int rr)//ll,rr分别指x,y
{
   if(ll<=l&&r<=rr) return SUM[k];//边界条件，访问区间包括当前区间返回该和。
   int mid=(l+r)/2,sum=0;
   if(ll<=mid) sum+=Find(l,mid,2*k,ll,rr);
   if(rr>=mid+1) sum+=Find(mid+1,r,2*k+1,ll,rr);
   return sum;
}

【C++】线段树（二）