|
线段树（Segment Tree）
文章目录
线段树（Segment Tree）一、创建线段树二、修改arr[]元素，更新tree[]元素值三、求区间和四、时间复杂度降为O(logn)五、完整代码
一、创建线段树
 
//创建线段树
void buildtree(int arr[],int tree[],int node,int start,int end){
//递归到树的叶子结点、结点值为单个数组元素
if(start==end)
//修改tree数组结点值
tree[node]=arr[start];
else{
//区间分段点
int mid=(start+end)/2;
//左右结点下标(层序，根结点下标为0)
int left_node=node*2+1;
int right_node=node*2+2;
//创建左右子树
buildtree(arr,tree,left_node,start,mid);
buildtree(arr,tree,right_node,mid+1,end);
//修改根结点的值(根结点=左结点+右结点)
tree[node]=tree[left_node]+tree[right_node];
}
}
二、修改arr[]元素，更新tree[]元素值
 
//修改数组元素，arr[idx]=val
void update(int arr[],int tree[],int node,int start,int end,int idx,int val){
//找到待修改结点arr[idx],从叶子结点往上依次修改tree数组元素
if(start==end){
arr[idx]=val;
tree[node]=val;
}
else
{
int mid=(start+end)/2;
int left_node=node*2+1;
int right_node=node*2+2;
//寻找待修改元素的下标idx所在的区间
//idx在左区间
if(idx>=start&&idxR||L>end)
return 0;
//[start-end]在[L,R]之内，当前结点即为[start-end]区间和，
//没必要递归至叶结点，直接返回结点值
if(Lend)
return 0;
//[start-end]在[L,R]之内，当前结点即为[start-end]区间和，
//没必要递归至叶结点，直接返回结点值
if(Ln;
int arr[n];
for(int i=0;i>arr[i];
buildtree(arr,tree,0,0,n-1);
//创建线段树
for(int i=0;i |