线段树

朱雀 2023-07-10 12:39 24阅读 0赞

## 线段树：创建时实际做的是后序遍历 ##

> 1.  线段树不是完全二叉树
> 2.  线段树是平衡二叉树
> 3.  堆也是平衡二叉树，故完全二叉树是平衡二叉树，平衡二叉树不一定是完全二叉树。
> 4.  引入的意义：对区间进行操作（区间染色、区间计算…）
> 5.  线段树中的结点是保存的一个区间的计算值/一个区间。

### 相关点： ###

#### 1. 平衡二叉树 ####

> 最小深度和最大深度相差为1

#### 2. 如果用数组创建线段树，则需要4n个空间。 ####

> 由于线段树每个结点都保存的是一个区间的相关值，故要为一个集合中的区间进行划分，如果该集合的长度为偶数，则刚好能够划分为一个满二叉树，而最后一行的叶子结点的个数为`2的k次方`（k为深度，根结点的深度为0），而前k-1行总共大约为`2的k次方`，故当集合中元素个数为偶数时，需要`2n`个数组空间。而如果个数是奇数，则需要`4n`个数组空间。故为了满足奇偶个元素，则需要申请4n个空间（当然会浪费许多空间）

#### 3. 如果用链表存储线段树，则不会浪费太多空间，需要多少结点则添加多少结点。 ####

#### 4. 当进行区间更新时，可以利用线段树的懒惰更新思想来降低算法复杂度。（不采用懒惰更新思想的算法复杂度为`O(n)`）. ####

> 在第一次更新时并不更新所有叶子结点，只更新具体的区间结点的值。当下一次更新/访问时才从待更新数组中将未更新的结点更新再进行此次操作。

#### 5. 二维线段树 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70]

#### 6. 动态线段树：用链表创建线段树 ####

> 根据所需区间动态划分线段树。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 1]

#### 7. 线段树的相关操作： ####

##### ① 线段树的创建（复杂度为`O(n)`，实际为4n） #####

interface Merger { 
        merge(left: any, right: any): any;
    }
    class SegementTree<T>{ 
        private tree: T[];//构建的线段树，如果为偶数，实际上最多需要2n，如果为奇数，实际上最多需要4n
        private saveArr: T[];//初始数据集合
        private merger: Merger;
        constructor(arr: T[], merger: Merger) { 
            this.tree = new Array(4 * arr.length);
            this.saveArr = arr;
            this.merger = merger;
            this.setTree(0, 0, arr.length - 1);
        }
        private setTree(treeIndex: number, L: number, R: number): void { 
            if (L == R) { 
                this.tree[treeIndex] = this.saveArr[L];
                return;
            }
            let mid: number = Math.floor(L+(R - L) / 2);//前多后少
            let left = this.getLeftIndex(treeIndex);
            let right = this.getRightIndex(treeIndex);
            this.setTree(left, L,mid);
            this.setTree(right,mid + 1, R);
            this.tree[treeIndex] = this.merger.merge(this.tree[left], this.tree[right]);//整合
        }
        public getSize(): number { 
            return this.saveArr.length;
        }
        public get(index: number): T { 
            if (index < 0 || index > this.saveArr.length - 1) { 
                throw new Error("非合理索引");
            }
            return this.saveArr[index];
        }
        private getLeftIndex(index: number): number { 
            return 2 * index + 1
        }
        private getRightIndex(index: number): number { 
            return 2 * index + 2;
        }
    class MergerSum implements Merger { 
        merge(left: any, right: any): any { 
            return left + right;
        }
    }

##### ② 区间查询（下述代码实现的是区间求和） #####

*  ###### 通过线段树实现 ######

//通过线段树实现
    //区间查询
        public getSegeList(startIndex:number,endIndex:number):any{ 
            if(startIndex<0 || endIndex>this.getSize()-1 || startIndex>this.getSize()-1 || endIndex<0){ 
                throw new Error("越界了")
            }else if(endIndex<startIndex){ 
                throw new Error("非合法区间");
            }
            return this.getList(0,0,this.getSize()-1,startIndex,endIndex);
        }
        private getList(treeIndex:number,sIndex:number,eIndex:number,startIndex:number,endIndex:number):any{ 
            if(sIndex==startIndex && endIndex == eIndex){ 
                return this.tree[treeIndex];
            }
            let mid = Math.floor(sIndex+(eIndex-sIndex)/2);
            let leftChildIndex = this.getLeftIndex(treeIndex);
            let rightChildIndex = this.getRightIndex(treeIndex);
            if(endIndex<=mid){ 
                return this.getList(leftChildIndex,sIndex,mid,startIndex,endIndex);
            }else if(startIndex>mid){ 
                return this.getList(rightChildIndex,mid+1,eIndex,startIndex,endIndex);
            }
            let leftArr = this.getList(leftChildIndex,sIndex,mid,startIndex,mid);
            let rightArr = this.getList(rightChildIndex,mid+1,eIndex,mid+1,endIndex);
            return this.merger.merge(leftArr,rightArr);
        }

*  ###### 通过数组实现：创建一个`sum`数组，`sum[i]`存储的是前`i`个元素的和。如果求`[i,j]`区间的和，则只需要`sum[j]-sum[i]+arr[i]` ######

//通过数组实现
    var NumArray = function(nums) { 
        this.array = nums;
        this.sum = new Array(nums.length);
        for(let i=0;i<nums.length;i++){ 
            if(i==0){ 
                this.sum[i] = nums[i];
                continue;
            }
            this.sum[i] = this.sum[i-1]+nums[i];
        }
    };
    NumArray.prototype.sumRange = function(i, j) { 
        return this.sum[j]-this.sum[i]+this.array[i];
    };

##### ③ 更新某一元素的值 #####

*  ###### 通过线段树实现 ######

public update(index:number,val:T):void{ 
            if(index>this.tree.length){ 
                throw new Error("越界了")
            }
            this.updateVal(0,0,this.tree.length-1,val,index);
        }
        private updateVal(treeIndex:number,l:number,r:number,val:T,index:number){ 
            if(l==r){ 
                this.tree[treeIndex] = val;
                return;
            }
            let mid = Math.floor(l+(l-r)/2);
            let leftIndex = this.getLeftIndex(treeIndex);
            let rightIndex = this.getRightIndex(treeIndex);
            if(index<=mid){ 
                this.updateVal(leftIndex,l,mid,val,index);
            }else{ 
                this.updateVal(rightIndex,mid+1,r,val,index);
            }
            this.tree[treeIndex] = this.merger.merge(this.tree[leftIndex],this.tree[rightIndex]);
        }

*  ###### 通过数组实现 ######

RMQ问题经典解决思路

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030214223782.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200302142223978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng==,size_16,color_FFFFFF,t_70