线段树专题

线段树专题

线段树说明及理解

  • 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
    • 预处理耗时O(n),查询、更新操作O(logn),需要额外的空间O(n)即2倍空间
  • 未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。
  • 区间修改(比如给[l,r]区间所有的值都加上add值的操作),采用lazy标记,即不直接给区间所有的值进行操作。

图解(二分思想)

  • 10个数:3,7,3,2,12,4,7,9,22,1
  • 初始状态
    • root = 1
    • [1, 10]

      其中一号结点为线段树的根节点,最底层一排结点对应的值为我们上述10个数,此时底层结点的下标还不知道。
  • 第一次分解
    • mid = (1+10)/2 = 5
    • root2 = root x 2 = 2, root3 = root x 2+1 = 3
    • [1, 5], [6, 10]
  • 第二次分解

    • mid = (1+5)/2 = 5, mid = (6+10)/2 = 8
    • root4 = root2 x 2 = 4, root5 = root2 x 2+1 = 5
    • root6 = root3 x 2 = 6, root7 = root3 x 2+1 = 7
    • [1, 3],[4,5], [6, 8], [9, 10]
  • 依次类推,最终结果如下图

代码编写:

  • 变量定义

    1
    2
    3
    const int maxn = 5e4+7;
    int tree[maxn*4]; // 4倍空间
    int lazy[maxn*4]; // lazy标记,区间修改用的
  • PushUp函数,用于合并

    1
    2
    3
    4
    5
    6
    void PushUp(int root){
    tree[root] = tree[root<<1]+tree[(root<<1)|1];
    //求和 = 左子树+右子树
    // 如果是求最值就是 = max(tree[root<<1],tree[(root<<1)|1)
    return ;
    }
  • PushDown函数,lazy处理,用于向下传递lazy值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void PushDown(int root , int l, int r){
    if(!lazy[root]) return ; //为空,无lazy值,无须传递
    int mid = (l+r)>>1; // 二分
    tree[root<<1] += lazy[root]*(mid-l+1); //lazy*区间长度

    tree[(root<<1)|1] += lazy[root]*(r-mid); // lazy*区间长度

    lazy[root<<1] += lazy[root]; // 左子树加上lazy值
    lazy[(root<<1)|1] += lazy[root];//右子树加上lazy值

    lazy[root] = 0; //将当前的根节点的lazy置0,因为lazy已经传递到左右子树了
    }
  • 建树build tree

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void build(int root, int left, int right){
    if(left == right) {
    scanf("%d", &tree[root]); //到达底层结点
    } else {
    int mid = (left+right) >>1; // x>>1是位运算,表示x除以2

    build(root<<1, left, mid); // 左子树,见图解
    build((root<<1)|1, mid+1, right); // |1是位运算,表示将二进制下的末尾设置为1,在此场景下,即+1操作,右子树,见图解

    // 计算出左右子树的值后就可以计算根节点的值了

    PushUp(root);

    }
    return ;
    }
    //应用:build(1, 1, n);
  • 区间sum查询

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //[l, r]表示当前查询区间
    //[left, right]表示目标查询区间

    int query(int root,int l, int r, int left, int right){
    if(r<left || l>right) return 0; // 不在目标区间范围内直接退出查询
    else if(l>=left && r<=right){ //是目标区间的子区间,直接返回这个区间的值即可
    return tree[root];
    } else {

    // PushDown(root, l, r); 若有区间修改则要调用此函数

    int mid = (l+r)>>1;

    int ls = query(root<<1, l, mid, left, right); //查询左区间
    int rs = query((root<<1)|1, mid+1, r, left, right);//查询右区间

    return ls+rs;
    }
    }
    // 应用:query(1, 1, n, x, y);
    // x,y表示目标区间
  • 单点更新

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // [l, r]表示查询区间
    // inx表示更新的下标
    // add表示更新值(+或者-)
    void update(int root, int l, int r, int inx, int add){
    if(l == r) { // 查找到了该点,更新该点对应的tree[root]值后返回
    tree[root] += add;
    return ;
    }

    int mid = (l+r)>>1;
    // 二分法去查找目标结点
    if(inx <= mid){
    update(root<<1, l, mid, inx, add);
    } else {
    update((root<<1)|1, mid+1, r, inx, add);
    }

    // 通过左右子树更新当前root下的值,见图解
    tree[root] = tree[root<<1]+tree[(root<<1)|1];
    return ;
    }
    //应用:update(1, 1, n, inx, add)
  • 区间更新

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //lazy标记 , add表示区间每个元素加上add值(可正负)
    void UpdateLR(int root, int l, int r, int left, int right, ll add){
    if(l>right || r < left) return ;

    if(left<=l && r <= right){
    lazy[root] += add;
    tree[root] += add*(r-l+1);
    return ;
    }

    int mid = (l+r) >> 1;
    PushDown(root, l, r);

    UpdateLR(root<<1, l, mid, left, right, add);

    UpdateLR((root<<1)|1, mid+1, r, left, right, add);

    PushUp(root);
    }