数据结构笔记_线段树

一.为什么要使用线段树

对于一类特殊的问题，我们关心的是线段（或者区间）

问题1：

问题2（对问题1进行抽象）对一段区间的更新与查询操作：

线段树解决的实际问题，区间固定，区间内的数据会发生变化，对区间内的数据进行更新和查询的操作

二.线段树

• 线段树的结构，每个节点中存储的是一段区间内的某种统计值（如，求和）

• 平衡二叉树：是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
• 线段树不是完全二叉树，但它是一种平衡二叉树（完全二叉树一定是平衡的，堆是完全二叉树，平衡二叉树不会退化成链表）

• 与完全二叉树相似，平衡二叉树也可以用数组来表示（非节点的形式），思路是将其看作是满二叉树 (不存在的节点存储“null”)
• 对于满二叉树，有一个特性：最后一层的节点数大致等于前面所有层节点之和
• 线段树通常不考虑添加元素，如果区间中有n个元素，则相应的存储线段树的数组最多需要4n个静态存储空间（最坏情况：n=2^k+1,此时，浪费了近一半的空间）

• 线段树的三个操作（建树，查询，更改） ，递归方式实现

//递归实现创建表示线段树的数组
    //递归宏观语义：在线段树数组中索引为treeIndex处，存放数据数组中区间为[l, r]的数据的统计量,即tree[treeIndex]中存储的是data[l...r]的统计量
    //data[]是数据数组，tree[]是将data中的数据组织成树结构的数组，因为要做统计，tree的长度为最坏情况下为data的4倍
    private void buildSegmentTree(int treeIndex, int l, int r){
        //递归到底时
        if(l == r){
            tree[treeIndex] = data[l];
            return;
        }

        int mid = l+(r-l)/2;
        buildSegmentTree(leftChild(treeIndex), l, mid);
        buildSegmentTree(rightChild(treeIndex), mid+1, r);

        //根据具体业务，将左右节点的统计量融合成根节点的统计量
        tree[treeIndex] = merger.merge(tree[leftChild(treeIndex)], tree[rightChild(treeIndex)]);
    }


//注：leftChild(treeIndex) = 2*treeIndex+1
//   rightChild(treeIndex) = 2*(treeIndex)+1
           

//线段树的查询
    public E query(int queryL, int queryR){
        if(queryL<0 || queryL>data.length-1 || queryR<0 || queryR>data.length-1 || queryL>queryR){
            throw new IllegalArgumentException("index is illegal");
        }

        return query(0, 0, data.length-1, queryL, queryR);
    }
    //递归实现查询
    // 从以treeIndex为根的节点（此节点存储着[l,r]数据的统计量）搜索存储着区间[queryL, queryR]的统计量的节点
    private E query(int treeIndex, int l, int r, int queryL, int queryR){
        //递归退出条件
        if(l==queryL && r==queryR){
            return tree[treeIndex];
        }

        int mid = l+(r-l)/2;
        if(queryL>=mid+1){
            return query(rightChild(treeIndex),mid+1,r, queryL, queryR);
        }else if(queryR<=mid){
            return query(leftChild(treeIndex), l, mid, queryL,queryR);
        }else{
            E leftRes = query(leftChild(treeIndex), l, mid, queryL, mid);
            E rigttRes = query(rightChild(treeIndex), mid+1, r, mid+1, queryR);
            return merger.merge(leftRes, rigttRes);
        }
    }
           

//更新某个元素,更新数据数组中的某个元素
    public void set(int index, E e){
        if(index<0 || index>=data.length){
            throw new IllegalArgumentException("index is illegal!");
        }
        data[index] = e;
        //对应需更新表示线段树的数组中的元素
        set(0, 0, data.length-1, index, e);
    }
    //递归实现，修改线段树中某个元素
    private void set(int treeIndex, int l, int r, int index, E e){
        if(l == r){
            tree[treeIndex] = e;
            return;
        }

        int mid = l+(r-l)/2;
        if(index>mid+1){
            set(rightChild(treeIndex),mid+1, r, index, e);
        }else{
            set(leftChild(treeIndex), l ,mid, index, e);
        }
        tree[treeIndex] = merger.merge(tree[rightChild(treeIndex)], tree[leftChild(treeIndex)]);
    }
           

三.线段树的高层次扩展

• 对某一个区间内的数据进行更新：懒惰更新

• 二维线段树

• 动态线段树，通过链式节点的方式实现，节点内存储区间范围，区间内元素的统计值，以及左右子节点。很好的解决底层基于数组的线段树的4n的空间开销。

• 关于区间操作的另外一个重要的数据结构：树状数组（Binary Index Tree）
• 一些区间的相关问题，不一定非要依赖于数据结构来处理，如 RMQ (Range Minimum Query) 问题，有许多经典的思路