区间树入门以及模板代码
导语：笔者最近在回顾和学习以前学习的算法，希望能够有更好的收获。写这篇博客旨在深入理解区间树的内涵以及编写区间树的模板代码。
1、区间树：区间相关问题的解答
区间树常用于在一维数组的特定区间对查询进行快速回复，区间树的最简单的应用就是求区间最小值的问题。区间树的基本思路是：生成表示给定数组各区间的二叉树，区间树的根区间总是表示整个区间][0,n-1]，而一个树结构的左侧后代节点和右侧后代节点分别表示该区间的左半侧[0,(0+n-1)/2]和右半侧[(0+n-1)/2+1,n-1]，区间树的叶子点表示区间为1。
因为我们是把一维数组构造成二叉树，所以我们查找的区间个数最多不超过log(n)。对于查找不需要O(log(n))的运行时间，只需要o(log(n))的时间就能够回复此类查询。
2、区间树的表示方法
首先，我们要考虑如何考虑节点，区间树是一颗几乎被“填满”的二叉树，这种二叉树能够节省空间，用根节点表示数组的1号元素，那么左侧后代节点和右侧后代节点分别为node*2和node*2+1。这样我们就能够把区间树的信息保存为一维数组，我们直接去4*n的一维数组大小表示区间树的长度。
3、初始化区间树
接下来我们来编写初始化区间树的代码，初始化逻辑很简单：
1、如果到了叶子节点，则初始化改rangeMin(node) = arry[left]; 返回该叶子节点的值，否则到2；
2、获取递归左子树(left,(left+right)/2,node*2)的值与递归右子树((left+right)/2+1,right,node*2+1)的值的最小值min。
3、初始化当前node的值为min。返回该值。
部分核心代码如下：
struct RMQ{
//数组长度
int n;
//各区间最小值
vector<int> rangeMin;
RMQ(const vector<int>&arry){
n = arry.size();
rangeMin.resize(n*4);
init(arry,0,n-1,1);
}
/**
1、如果到了叶子节点，则初始化改rangeMin(node) = arry[left];
返回该叶子节点的值，否则到2；
2、获取递归左子树(left,(left+right)/2,node*2)的值与递归右子树
((left+right)/2+1,right,node*2+1)的值
的最小值,min。
3、初始化当前node的值为min。返回该值
*/
int init(const vector<int> &arry,int left,int right,int node){
//如果市叶子节点那么我们直接赋值
if(left==right){
return rangeMin[node] = arry[left];
}
//递归左右子树获得取值
int mid = (left+right)/2;
int leftMin = init(arry,left,mid,node*2);
int rightMin = init(arry,mid+1,right,node*2+1);
return rangeMin[node] = min(leftMin,rightMin);
}
};接着我们分析时间复杂度，每个节点耗费的时间时O(1)，所以整个初始化的时间复杂度是O(n)。
3、区间树的查询处理
完成初始化工作以后，我们就可以求任意区间的最小值，这种过程就是区间树的查询(query)，我们要查询[i,j]区间的最小值，在子树区间中[nl,nr]，存在三种情况：
1、我们的子树区间与查找区间没有交集，那么我们直接忽略，因为这个子树区间的值根本不在[i,j]内。
2、当我们的子树区间[nl,nr]包含于[i,j]查找区间时，我们直接返回初始化过程中该子树区间的最小值即可。
3、我们的子树区间与查找区间存在交集，但是不是包含关系，那么我们只需要得到该子树区间的左右子树区间的最小值返回即可，
实现算法如下：
1、我们的范围[l,r]与i,j没有交集，直接忽略，返回int类型表示 的最大值即可。
2、[l,r]包含于[i,j]直接返回我们的node值。
3、存在交集，但是我们的 [l,r]没有包含于[i,j],递归调用左右子树，返回左右子树递归的最小值。
核心代码：
/**
求解给定区间[i,j]中的最小值：
有三种情况:
1、我们的范围[l,r]与i,j没有交集，直接忽略，返回int类型表示
的最大值即可。
2、[l,r]包含于[i,j]直接返回我们的node值。
3、存在交集，但是我们的 [l,r]没有包含于[i,j],递归调用左右
子树，返回左右子树递归的最小值。
*/
int query(int l,int r,int node ,int nl,int nr){
//判断第一种情况
if(r<nl||l>nr){
return INF;
}
//判断第二种情况,包含了叶子节点的情形
if(nl>=l&&nr<=r){
return rangeMin[node];
}
int mid = (nl+nr)/2;
int leftMin = query(l,r,node*2,nl,mid);
int rightMin = query(l,r,node*2+1,mid+1,nr);
return min(leftMin,rightMin);
}
//暴露查询接口
int getQuery(int l,int r){
return query(l,r,1,0,n-1);
}接着我们分析时间复杂度，由于我们查找的时二叉搜索树，我们的非叶子节点个数一定小于log(n)，所以我们的时间复杂度我为O(log(n))。
4、更新区间树
假如我们要修改我们一维数组的值，那么我们也需要更新我们的区间树，很容易想到，由于不同的非叶子节点所代表的区间没有交集，所以我们只需要更新我们的index所在的节点区间即可，而不需要去更新不包含index的节点，算法与区间树的查询处理类似，只是我们的查询区间长度变成了1。时间复杂度为O(log(n))。
这里给出我们模板类的所有代码：
#include <iostream>
#include<vector>
using namespace std;
const int INF = 1<<30;
struct RMQ{
//数组长度
int n;
//各区间最小值
vector<int> rangeMin;
RMQ(const vector<int>&arry){
n = arry.size();
rangeMin.resize(n*4);
init(arry,0,n-1,1);
}
/**
1、如果到了叶子节点，则初始化改rangeMin(node) = arry[left];
返回该叶子节点的值，否则到2；
2、获取递归左子树(left,(left+right)/2,node*2)的值与递归右子树
((left+right)/2+1,right,node*2+1)的值
的最小值,min。
3、初始化当前node的值为min。返回该值
*/
int init(const vector<int> &arry,int left,int right,int node){
//如果市叶子节点那么我们直接赋值
if(left==right){
return rangeMin[node] = arry[left];
}
//递归左右子树获得取值
int mid = (left+right)/2;
int leftMin = init(arry,left,mid,node*2);
int rightMin = init(arry,mid+1,right,node*2+1);
return rangeMin[node] = min(leftMin,rightMin);
}
/**
求解给定区间[i,j]中的最小值：
有三种情况:
1、我们的范围[l,r]与i,j没有交集，直接忽略，返回int类型表示
的最大值即可。
2、[l,r]包含于[i,j]直接返回我们的node值。
3、存在交集，但是我们的 [l,r]没有包含于[i,j],递归调用左右
子树，返回左右子树递归的最小值。
*/
int query(int l,int r,int node ,int nl,int nr){
//判断第一种情况
if(r<nl||l>nr){
return INF;
}
//判断第二种情况,包含了叶子节点的情形
if(nl>=l&&nr<=r){
return rangeMin[node];
}
int mid = (nl+nr)/2;
int leftMin = query(l,r,node*2,nl,mid);
int rightMin = query(l,r,node*2+1,mid+1,nr);
return min(leftMin,rightMin);
}
//暴露查询接口
int getQuery(int l,int r){
return query(l,r,1,0,n-1);
}
/**
区间树更新节点：
当array更新时，我们只需要更新包含了该节点的子树即可。
1、当到达叶子节点时，我们直接更新叶子节点即可。
2、当index在[nl,nr]之中时，我们更新当前节点为左右子树
的最小值。
*/
int upDate(int index,int newValue,int node,int nl,int nr){
//不在区间内
if(index<nl||index>nr){
return INF;
}
//是否是叶子节点
if(nl==nr){
return rangeMin[node] = newValue;
}
//调用左右子树
int mid = (nl+nr)/2;
int leftMin = upDate(index,newValue,node*2,nl,mid);
int rightMin = upDate(index,newValue,node*2+1,mid+1,nr);
return rangeMin[node] = min(leftMin,rightMin);
}
//暴露更新接口
updateRMQ(int index,int newValue){
upDate(index,newValue,1,0,n-1);
}
};
int main()
{
cout << "Hello world!" << endl;
return 0;
}