线段树(Segment Tree)

﹏ヽ暗。殇╰゛Y 2022-05-24 03:44 219阅读 0赞

线段树本质上还是二叉树, 不同的是它的每个节点记录了一段区间的信息.  
所以很多算法的实现还是大量的递归, 二分的思路.

## 实现 ##

#### 用结构体来保存节点 ####

节点中除了left, right之外, 根据实际情况添加信息, 此处以区间和, 区间最小值, 区间最大值为例

typedef struct {
        int left;//区间左边界
        int right;//区间右边界
        int sum;
        int min;
        int max;
    } Tree;
    //用数组保存二叉树2 * i, 2 * i + 1分别表示左右子节点
    //一般来说数组大小为SIZE, 线段树大小最好为4 * SIZE (我也不知道为什么 可以用二叉树的知识推一推)
    Tree trees[4 * SIZE];

#### 建树 ####

假如数组大小为n, 调用build(1, 1, n), 此处为了方便写代码, 不使用数组0下标  
pushUp函数自下往上更新节点信息, 后面更新时也会用到  
`i * 2` 可以用`i<<1`代替, `i * 2 + 1`可以用`i<<1|1`代替, `(left + right) / 2` 可以写成`(left + right)>>1`. 据说位数算的速度更快.

/** * 根据子节点信息更新父节点 * @param root 当前节点 */
    void pushUp(int root) {
        trees[root].sum = trees[root * 2].sum + trees[root * 2 + 1].sum;
        trees[root].max = max(trees[root * 2].max, trees[root * 2 + 1].max);
        trees[root].min = min(trees[root * 2].min, trees[root * 2 + 1].min);
    }
    
    /** * @param root 当前节点 * @param left 节点左边界 * @param right 节点右边界 */
    void build(int root, int left, int right) {
        trees[root].left = left;
        trees[root].right = right;
        if (left == right) {
            //对节点初始化 假设处理的为数组a
            trees[root].sum = trees[root].max = trees[root].min = a[left];
            return;
        }
        int mid = (left + right) / 2;
        build(root * 2, left, mid);
        build(root * 2 + 1, mid + 1, right);
        //上面两个递归调用结束之后表示两个子节点已经建树完成 可以用子节点信息更新当前节点
        pushUp(root);
    }

## 点更新 ##

对数组中某个单点的更新

/** * @param pos 更新的位置 此处假设调用函数时pos的值一点正确 函数内部没有错误处理 * @param val 更新的值 */
    void update(int root, int pos, int val) {
        int rootLeft = trees[root].left;
        int rootRight = trees[root].right;
        if (rootLeft == rootRight) {
            trees[root].sum = trees[root].min = trees[root].max = val;
            return;
        }
        int mid = (rootRight + rootLeft) / 2;
        if (pos <= mid)
            update(root * 2, pos, val);
        else if (pos > mid)
            update(root * 2 + 1, pos, val);
        pushUp(root);//同样要向上更新
    }

## 区间更新 ##

区间更新可能是线段树基本操作中比较难理解的部分.  
为了提高效率此处采用懒操作, 简单地说就是先标记需要的时候再更新, 不需要就不更新.  
此处以区间加法为例.如对区间`[left, rigt]`的数都加上val  
当更新到了某个完整区域即`rootLeft >= left && rootRight <= right`(root为当前节点), 对当前节点进行标记, 不再继续往下更新, `add[root] += val`, 当其他更新, 或者查询操作涉及到该区间的*子区间* (注意是子区间)再继续往下更新.

//也可以把add保存到结构体当中, 表示它的子节点没有进行的更新
    int add[SIZE * 4];
    /** * 向下更新 */
    void pushDown(int root) {
        if (add[root]) {
       //add[root]不为0 表示子节点有更新
            int addVal = add[root];
            //此处同样只是更新两个子节点 标记后就不再往下更新
            add[root * 2] += addVal;
            add[root * 2 + 1] += addVal;
            int rootLeft = trees[root].left;
            int rootRight = trees[root].right;
            int mid = (rootLeft + rootRight) / 2;
            trees[root * 2].sum += addVal * (mid - rootLeft + 1);
            trees[root * 2 + 1].sum += addVal * (rootRight - mid);
            add[root] = 0;//子节点更新完成, 取消标记
        }
    }
    
    /** * 对区间[left, right]中的元素都加上val */
    void update(int root, int left, int right, int val) {
        int rootLeft = trees[root].left;
        int rootRight = trees[root].right;
        if (rootLeft >= left && rootRight <= right) {
            //更新到一个完整区域了 对当前节点的信息更新
            //此处仅更新sum为例 max, min也可以类似更新
            trees[root].sum += val * (rootRight - rootLeft + 1);
            //对次节点标记表示它的子节点没有更新 之后return不再向下更新
            add[root] += val;
            return;
        }
        int mid = (rootLeft + rootRight) / 2;
        //上面if的条件不满足 表示当前节点的区域不是更新区域的子区域 所以需要向下更新
        pushDown(root);
        if (right <= mid)
            update(root * 2, left, right, val);
        else if (left > mid)
            update(root * 2 + 1, left, right, val);
        else {
            update(root * 2, left, mid, val);
            update(root * 2 + 1, mid + 1, right, val);
        }
        //此处仅仅以sum为例 实际可能会更新min, max
        trees[root].sum = trees[root * 2].sum + trees[root * 2 + 1].sum;
        //pushUp(root);
    }

## 区间查询 ##

#### 最值查询 ####

此处以最大值为例, 最小值写法类似  
思路就是完整区间就直接返回最值, 不是完整区间就向下查询子区间, 最后再对结果取最值

/** *查询[left, right]中的最大值 */ 
    int queryMax(int root, int left, int right) {
        int rootLeft = trees[root].left;
        int rootRight = trees[root].right;
        if (rootLeft == left && rootRight == right)
            return trees[root].max;
        int mid = (rootLeft + rootRight) / 2;
        //如果涉及到区间更新了 此处需要向下更新
        //pushDown(root);
        if (right <= mid)
            return queryMax(root * 2, left, right);
        else if (left > mid)
            return queryMax(root * 2 + 1, left, right);
        else
            return max(queryMax(root * 2, left, mid), 
            queryMax(root * 2 + 1, mid + 1, right));
    }

#### 区间和查询 ####

思路和上面一样, 只是注意要取子区间返回的和

int querySum(int root, int left, int right) {
        if (trees[root].left == left && trees[root].right == right)
            return trees[root].sum;
        int mid = (trees[root].left + trees[root].right) / 2;
        //如果涉及到区间更新了 此处需要向下更新
        //pushDown(root);
        if (right <= mid)
            return querySum(root * 2, left, right);
        else if (left > mid)
            return querySum(root * 2 + 1, left, right);
        else
            return querySum(root * 2, left, mid) + querySum(root * 2 + 1, mid + 1, right);
    }