基于完全二叉树实现线段树-- [爆竹声中一岁除,线段树下苦踌躇]

一.完全二叉树

• 完全二叉树的物理结构是线性表,逻辑结构是二叉树
  

完全二叉树的父子结点引索关系

• 通过子结点下标引索父结点下标 : 父结点下标 = 子节点下标/2;
• 通过父结点下标引索左孩子下标 : 左孩子下标 = 父结点下标 * 2;
• 通过父结点下标引索右孩子下标 : 右孩子下标 = (父结点下标 * 2) + 1;
  

二.线段树

• 线段树是一种基于分治思想实现的数据结构,用途非常广泛,常用于快速引索和动态更新数组的区间和,以及解决众多类型的区间问题
• 现有一个原数组,线段树结点表示一个结构体,结构体中存储原数组某一段区间的端点下标和区间和

struct TreeNode{
	int left;   //原数组区间左端点下标
	int right;  //原数组区间右端点下标
	int Sum;    //区间和
}

• 线段树根节点存储整个原数组的区间和,然后以区间二分的方式构建左子结点和右子结点:
  
• 以此类推,形成递归,直到将原数组区间划分为一个个单元素区间为止:
  
• 建树过程时间复杂度为O(N),引索更新的复杂度都是logN,比如要引索原数组[1,4]的区间和:
  

三.基于完全二叉树实现线段树

关于线段树的结点数量问题的证明

• 证明:若根节点的区间长度为N,线段树的总结点数量不会超过4*N：
  
• 使用线段数时,数据范围为N,则定义一个4*N大小的完全二叉树数组防止算法中出现数组越界问题

递归建树

• int BuildTree(TreeNode * Tree,int index,int left,int right)
  • 调用BuildTree(Tree,1,left,right)从下标1(根节点)开始递归建立线段树,[left,right]表示原数组的区间
  • 返回值表示原数组[left,right]的区间和

void Bulid(TreeNode* Tree,int index , int left , int right){
    //结点赋值
    Tree[index] = {left,right,0};
    if(right == left)return;
    //二分区间
    int mid = ((right - left) >> 1) + left;
    //构建左子树
    Bulid(Tree,index << 1,left, mid);
    //构建右子树
    Bulid(Tree,(index << 1)|1, mid + 1 , right);
}

• 递归建树的时间复杂度为O(N)

递归查询区间和

• int Get_Sum(TreeNode* Tree,int index , int left , int right)表示查询原数组[left,right]的区间和

//查询区间和
int Get_Sum(TreeNode* Tree,int index , int left , int right){
    //当前区间被目标区间包含则返回区间部分和
    if(Tree[index].left >= left && Tree[index].right <= right){
        return Tree[index].Sum;
    }
    //二分查询左右子树
    int mid = (Tree[index].left + Tree[index].right) >> 1;
    int res = 0;
    if(mid >= left) res = Get_Sum(Tree,index << 1,left,right);
    if(mid < right) res += Get_Sum(Tree,index << 1 | 1 , left , right);
    return res;
}

• 关于复杂度的分析:
  

递归单点修改

• void modify(TreeNode* Tree,int index,int target,int change),原数组下标为target的元素加上change,调用时index从1(根节点下标)开始递归

//原数组下标为target的元素加上change
void modify(TreeNode* Tree,int index,int target,int change){
    Tree[index].Sum += change;
    if(Tree[index].left  == Tree[index].right)return;
    //二分被修改区间
    int mid = (Tree[index].left + Tree[index].right) >> 1;
    if(target <= mid) modify(Tree,index << 1,target,change);  //递归修改左子树
    else modify(Tree,index << 1 | 1 , target,change);         //递归修改右子树
}

线段树模板题

线段树模板题1
线段树模板题2