世界热议:线段树

(资料图)

线段树--解决区间问题的数据结构，相比于树状数组，更具有普适性；

完全二叉树的性质：根节下标为1，，节点为 i 的节点，左子节点为2*i，右子节点为2*i+1；

代表nums中单个元素的节点tree[x]应当在树的最底层，即叶子节点；更大的区间从叶子节点开始向上构成；

代表区间【L，R】的节点 tree【i】，左子节点tree【2*i】表示区间【L，（L+R）/2】的区间和；右子节点tree【2*i+1】表示区间 【（L+R）/2 +1， R】的区间和；

初始化tree数组的大小 总是 令 其 为 4*n；类似于归并排序、快排的分治算法，将原问题不断的划分为左右子问题；

代码摘自：线段树从入门到急停 - 力扣（LeetCode）非常详细；

核心：一个就是注意单点修改时，递归结束条件的判断，是查询单点的话，就是 左右边界相等终止；查询区间和的话， 判断当前区间是否落在 所求范围内，是的话就加上这个区间；

另一个就是拓展：区间和数组可以替换为区间最值问题；求区间最大值、区间最小值等；

再一个就是区间修改问题，有两种，一种是增量式修改，因为注意到我们的区间和，若不关注每个具体的值，只是区间和的大小，我们无需每次都向下更新到叶子节点，否则会达到O(N)时间复杂度；因此 需要增加一个 数组，判断当前增量是否已经向下更新，我们称之为懒惰标记；； 第二种就是 覆盖式修改：将区间的值都修改为同一值，此时，我们不能依据增量式修改的方法，因为可能修改为0，而向下更新的标记 也是检查是否为0，从而 会产生冲突，所以另起一个数组，判断是否已经向下覆盖；；

代码实现：（此处将 两种修改方法写在一起了，建议分开写）

#include using namespace std;class Segement_tree{private:    vectornums;    vectortree;    vectorlazy;    vectoris_updated;    int n;    void pushUp(int i){        tree[i] = tree[2*i] + tree[2*i + 1];    }    void build(int left, int right, int i){        if(left == right){            tree[i] = nums[left];        }        int mid = (left + right) / 2;        build(left, mid, 2*i);        build(mid + 1, right, 2*i + 1);        pushUp(i);    }    /*单点修改*/    void add(int index, int x, int left, int right, int i){        if(left == right){            tree[i] += x;            return;        }        int mid = (left + right)/2;        if(index <= mid){            add(index,x,left,mid,2*i);        }else{            add(index,x,mid+1,right,2*i+1);        }        pushUp(i);    }    void update(int index,int x,int left, int right,int i){        if(left == right){            tree[i] = x;            return;        }        int mid = (left + right) /2;        if(index <= mid){            update(index,x,left,mid,2*i);        }else{            update(index,x,mid+1,right,2*i+1);        }        pushUp(i);    }    int query(int index,int left,int right, int i){        if(left == right) return tree[i];        int mid = (left + right) /2;        if(index <= mid){            return query(index,left,mid,2*i);        }else{            return query(index,mid+1,right,2*i+1);        }    }    /*区间求和*/    int sum(int left, int right, int s, int t, int i){        if(left <= s && t <= right) return tree[i];        int mid = (s + t) /2;        int res = 0;        if(left <= mid){            res += sum(left,right, s, mid, 2*i);        }        if(right > mid){            res += sum(left,right, mid+1, t, 2*i+1);        }        return res;    }    /*区间修改： 增量式 */    void add(int left, int right, int x,int s, int t, int i){        if(left <= s && t <= right){            tree[i] += (t-s+1)*x;            if(s != t) lazy[i] += x;            return;        }        int mid = (s + t)/2;        if(lazy[i] != 0) pushDown(s,mid,t,i);        if(left <= mid) add(left,right,x,s,mid,2*i);        if(right > mid) add(left,right,x,mid+1,t,2*i+1);        pushUp(i);    }    void pushDown(int s,int mid, int t,int i){        tree[2*i] += (mid-s+1)*lazy[i];        lazy[2*i] += lazy[i];        tree[2*i+1] += (t-mid)*lazy[i];        lazy[2*i+1] += lazy[i];        lazy[i] = 0;    }    /*区间修改： 覆盖式 */    void update(int left, int right,int x,int s,int t,int i){        if(left <= s && t <= right){            tree[i] = (t-s+1)*x;            if(s != t){                lazy[i] = x;                is_updated[i] = true;//未推送            }            return;        }        int mid = (s+t)/2;        if(is_updated[i]) pushDown1(s,mid,t,i);        if(left <= mid) update(left,right,x,s,mid,2*i);        if(right > mid) update(left,right,x,mid+1,t,2*i+1);        pushUp(i);    }    void pushDown1(int s,int mid,int t,int i){        tree[2*i] = (mid - s + 1)* lazy[i];        lazy[2*i] = lazy[i];        is_updated[2*i] = true;        tree[2*i+1] = (t - mid) * lazy[i];        lazy[2*i+1] = lazy[i];        is_updated[2*i+1] = true;        is_updated[i] = false;        lazy[i] = 0;    }public:    Segement_tree(vector& nums){        this->n = nums.size();        this->nums = nums;        this->tree.resize(4*n, 0);        this->lazy.resize(4*n, 0);        this->is_updated.resize(4*n, 0);        build(0, n-1, 1);    }    /*单点修改*/    void add(int index, int x){        add(index,x,0,n-1,1);    }    void update(int index,int x){        update(index,x,0,n-1,1);    }    int query(int index){        return query(index, 0, n-1,1);    }    /*区间求和*/    int sum(int left,int right){        return sum(left,right,0, n-1,1);    }    /*区间修改 ： 增量式*/    void add(int left,int right,int x){        add(left,right,x,0,n-1,1);    }    /*区间修改： 覆盖式 */    void update(int left,int right, int x){        update(left,right,x,0,n-1,1);    }};int main(){    system("pause");    return 0;}

关键词：