【模版】线段树详解

淩亂°似流年 2022-12-28 14:14 162阅读 0赞

### 文章目录 ###

*  线段树详解
 *   *  建树
     *  区间查询
     *  单点修改
     *  区间修改
     *  Lazy标记
 *  模版

--------------------

# 线段树详解 #

参考：https://blog.csdn.net/iwts\_24/article/details/81484561

**线段树是一颗满二叉树，有n个元素时，对区间的操作在O(logn)的时间内完成，初始化的操作时间和总的空间复杂度都为O(n)**

**常用于对区间的查询和修改操作**

## 建树 ##

const int MAX = 100005;
    int n;    //叶子结点的个数
    int dat[MAX << 2];    //一般为总节点个数的4倍
    
    //建树
    //外部调用build(1,1,n)，l,r为总的左右区间，node为当前所在的节点位置
    //递归的调用到叶子结点，再逐步返回求的父节点的值
    void build(int node, int l, int r)
    {
        
        if(l == r){
        	//当左区间和右区间相等时，到达叶子结点
            scanf("%d",&dat[node]);
            return;
        }
        int mid = (l + r) >> 1;
        build(node << 1, l, mid);	//递归到左子树
        build(node << 1 | 1, mid + 1, r);	//递归到右子树
        dat[node] = dat[node << 1] + dat[node << 1 | 1];	//回溯修改父节点
    }

## 区间查询 ##

//区间查询
    //查询区间[a,b]的总和
    //外部调用(a, b, 1, n, 1)
    //如果递归到区间[l,r]是在区间[a,b]内，那么就肯定是需要 加和 的部分
    //如果区间[l,r]与区间[a,b]无交集，那就总和就不变
    //如果区间[l,r]与区间只有一部分的交集，那么就判断区间[a,b]的两个端点与mid的关系，递归到更小的区间范围内去寻找总和
    int query_range(int a, int b, int l, int r, int node)
    {
        
          //区间[l,r]是在区间[a,b]内，那么就肯定是需要 加和 的部分，直接加和
        if(a <= l && b >= r)
            return dat[node];
        else{
        
          	//往下查询和时，需要将高层大区间的lazy标记下放
          	//因为查询的区间并不是高层大区间，而是大区间中的一部分
          	//因此需要将下面划分出来的小区间同步lazy标记，这样才能使得最后结果正确
            push_down(node, l, r);	
          	
            int mid = (l + r) >> 1;
            int sum = 0;
            //如果区间[a,b]存在部分区间在mid的左边，那么就要去区间[l,mid]中寻找，并加和
          	//此时节点到左孩子节点
            if(a <= mid)
                sum += query_range(a, b, l, mid, node << 1);
              
          	//如果区间[a,b]存在部分区间在mid的右边，那么就要去区间[mid + 1,r]中寻找，并加和
          	//此时节点到右孩子节点
            if(b > mid)
                sum += query_range(a, b, mid + 1, r, node << 1 | 1);
              
            return sum;
        }
    }

## 单点修改 ##

//单点修改
    //对index位置加上val值，l,r为总的左右区间，node为当前所在的节点位置
    //外部调用update(val, index, 1, n, 1)
    //采用二分的方法去寻找index下标，最后回溯修改父节点
    void update(int val, int index, int l, int r, int node)
    {
        
      	//当左区间和右区间相等时，到达叶子结点
      	//因为使用二分的思路去寻找，所以只要到达了l==r处，一定就是index位置
        if(l == r){
        	
            dat[node] += x;
            return;
        }
      	
      	//二分寻找
        int mid = (l + r) >> 1;
      	//如果index在区间[l,r]的mid的左边，就在区间[l,mid]去寻找index
      	if(index <= mid)
            update(x, index, l, mid, node << 1);
      	//如果index在区间[l,r]的mid的右边，就在区间[mid + 1,r]去寻找index
        else
            update(x, index, mid + 1, r, node << 1 | 1);
      	//二分寻找
      	
        dat[node] = dat[node << 1] + dat[node << 1 | 1];	//回溯修改父节点
    }

## 区间修改 ##

int lazy[MAX << 2];     //lazy标记，用于减少时间复杂度，区间修改时，不需要修改到叶子结点，
                            //只需要在对应的最大区间进行标记，最后在加和 或 其他操作时 再下放标记
    
    //区间修改
    //外部调用为update_range(a, b, val ,l ,r, node)
    //每次修改都只修改到能修改的最大区间！！！
    //如果区间[l,r]被区间[a,b]全包含，那么就意味着这个区间[l,r]是全部都要加上val的
    //那么就直接在这个区间上标记一个lazy标记，不再去下方遍历每个叶子结点增加val
    //采用二分的方法去寻找[a,b]区间，最后回溯修改父节点
    void update_range(int a, int b, int val, int l, int r, int node)
    {
        
      	//如果区间[l,r]被区间[a,b]全包含，那么就意味着这个区间[l,r]是全部都要加上val的
      	//那么就直接在这个区间上标记一个lazy标记，不再去下方遍历每个叶子结点增加val
        if(a <= l && b >= r){
        
            lazy[node] += val;
            dat[node] += (r - l + 1) * val;
            return;
        }
        else{
        
         		//修改值时，需要将可能的高层lazy标记下放
          	//使的下方的小区间的值为真实的值，最后累加才会正确
            push_down(node, l, r);
          
            int mid = (l + r) >> 1;
          	//二分去看区间[a,b]和mid的关系
          	//如果a <= mid，那就意味着[a,b]区间在区间[l,mid]中有需要修改的值
          	//那么就需要递归的到[l,mid]区间中去修改
          	//此时节点到左孩子节点
            if(a <= mid)
                update_range(a, b, val, l, mid, node << 1);
          
          	//如果b > mid，那就意味着[a,b]区间在区间[mid + 1,r]中有需要修改的值
          	//那么就需要递归的到[mid + 1,r]区间中去修改
          	//此时节点到右孩子节点
            if(b > mid)
                update_range(a, b, val, mid + 1, r, node << 1 | 1);
          
            dat[node] = dat[node << 1] + dat[node << 1 | 1];	//最后回溯，修改父节点的值
        }
    }

## Lazy标记 ##

//下放lazy标记
    //一般在区间查询和区间修改时需要使用到下放
    //调用为push_down(node, l ,r)
    //将大区间的lazy标记下放到小区间
    //并且在下放的过程中dat总和数组要加上这个lazy标记所新增的权制
    void push_down(int node, int l, int r)
    {
        
        if(lazy[node]){
        
            int mid = (l + r) >> 1;
          	
          	//将父节点的lazy标记下放到左右孩子节点
            lazy[node << 1] += lazy[node];	
            lazy[node << 1 | 1] +=lazy[node]; 
          	//将父节点的lazy标记下放到左右孩子节点
          
          	//同时在下方过程中，修改左右孩子的dat总和数组
          	//使得总和数组同步到加上lazy标记的情况下
            dat[node << 1] += (mid - l + 1) * lazy[node];
            dat[node << 1 | 1] += (r - mid) * lazy[node];
          
          	//因为高层大区间的lazy标记下放了
          	//高层大区间的lazy标记清零
            lazy[node] = 0;
        }
    }

--------------------

# 模版 #

//求总和的线段树
    
    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    const int MAX = 100005;
    int n;    //叶子结点的个数
    int dat[MAX << 2];    //一般为总节点个数的4倍
    int lazy[MAX << 2];     //lazy标记，用于减少时间复杂度，区间修改时，不需要修改到叶子结点，
                            //只需要在对应的最大区间进行标记，最后在加和 或 其他操作时 再下放标记
    
    //建树
    //外部调用build(1,1,n)，l,r为总的左右区间，node为当前所在的节点位置
    //递归的调用到叶子结点，再逐步返回求的父节点的值
    void build(int node, int l, int r)
    {
        
        if(l == r){
            //当左区间和右区间相等时，到达叶子结点
            scanf("%d",&dat[node]);
            return;
        }
        int mid = (l + r) >> 1;
        build(node << 1, l, mid);    //递归到左子树
        build(node << 1 | 1, mid + 1, r);    //递归到右子树
        dat[node] = dat[node << 1] + dat[node << 1 | 1];    //回溯修改父节点
    }
    
    //下放lazy标记
    //一般在区间查询和区间修改时需要使用到下放
    //调用为push_down(node, l ,r)
    //将大区间的lazy标记下放到小区间
    //并且在下放的过程中dat总和数组要加上这个lazy标记所新增的权制
    void push_down(int node, int l, int r)
    {
        
        if(lazy[node]){
        
            int mid = (l + r) >> 1;
          	
          	//将父节点的lazy标记下放到左右孩子节点
            lazy[node << 1] += lazy[node];	
            lazy[node << 1 | 1] +=lazy[node]; 
          	//将父节点的lazy标记下放到左右孩子节点
          
          	//同时在下方过程中，修改左右孩子的dat总和数组
          	//使得总和数组同步到加上lazy标记的情况下
            dat[node << 1] += (mid - l + 1) * lazy[node];
            dat[node << 1 | 1] += (r - mid) * lazy[node];
          
          	//因为高层大区间的lazy标记下放了
          	//高层大区间的lazy标记清零
            lazy[node] = 0;
        }
    }
    
    //单点修改
    //对index位置加上val值，l,r为总的左右区间，node为当前所在的节点位置
    //外部调用update(val, index, 1, n, 1)
    //采用二分的方法去寻找index下标，最后回溯修改父节点
    void update(int val, int index, int l, int r, int node)
    {
        
          //当左区间和右区间相等时，到达叶子结点
          //因为使用二分的思路去寻找，所以只要到达了l==r处，一定就是index位置
        if(l == r){
        
            dat[node] += val;
            return;
        }
          
          //二分寻找
        int mid = (l + r) >> 1;
        	// push_down(node,mid-l+1,r-mid); 若既有点更新又有区间更新，需要这句话
          //如果index在区间[l,r]的mid的左边，就在区间[l,mid]去寻找index
      		//此时节点到左孩子节点
        if(index <= mid)
            update(val, index, l, mid, node << 1);
          //如果index在区间[l,r]的mid的右边，就在区间[mid + 1,r]去寻找index
      		//此时节点到右孩子节点
        else
            update(val, index, mid + 1, r, node << 1 | 1);
          //二分寻找
          
        dat[node] = dat[node << 1] + dat[node << 1 | 1];    //回溯修改父节点
    }
    
    //区间查询
    //查询区间[a,b]的总和
    //外部调用(a, b, 1, n, 1)
    //如果递归到区间[l,r]是在区间[a,b]内，那么就肯定是需要 加和 的部分
    //如果区间[l,r]与区间[a,b]无交集，那就总和就不变
    //如果区间[l,r]与区间只有一部分的交集，那么就判断区间[a,b]的两个端点与mid的关系，递归到更小的区间范围内去寻找总和
    int query_range(int a, int b, int l, int r, int node)
    {
        
          //区间[l,r]是在区间[a,b]内，那么就肯定是需要 加和 的部分，直接加和
        if(a <= l && b >= r)
            return dat[node];
        else{
        
          	//往下查询和时，需要将高层大区间的lazy标记下放
          	//因为查询的区间并不是高层大区间，而是大区间中的一部分
          	//因此需要将下面划分出来的小区间同步lazy标记，这样才能使得最后结果正确
            push_down(node, l, r);	
          	
            int mid = (l + r) >> 1;
            int sum = 0;
            //如果区间[a,b]存在部分区间在mid的左边，那么就要去区间[l,mid]中寻找，并加和
          	//此时节点到左孩子节点
            if(a <= mid)
                sum += query_range(a, b, l, mid, node << 1);
              
          	//如果区间[a,b]存在部分区间在mid的右边，那么就要去区间[mid + 1,r]中寻找，并加和
          	//此时节点到右孩子节点
            if(b > mid)
                sum += query_range(a, b, mid + 1, r, node << 1 | 1);
              
            return sum;
        }
    }
    
    //区间修改
    //外部调用为update_range(a, b, val ,l ,r, node)
    //每次修改都只修改到能修改的最大区间！！！
    //如果区间[l,r]被区间[a,b]全包含，那么就意味着这个区间[l,r]是全部都要加上val的
    //那么就直接在这个区间上标记一个lazy标记，不再去下方遍历每个叶子结点增加val
    //采用二分的方法去寻找[a,b]区间，最后回溯修改父节点
    void update_range(int a, int b, int val, int l, int r, int node)
    {
        
      	//如果区间[l,r]被区间[a,b]全包含，那么就意味着这个区间[l,r]是全部都要加上val的
      	//那么就直接在这个区间上标记一个lazy标记，不再去下方遍历每个叶子结点增加val
        if(a <= l && b >= r){
        
            lazy[node] += val;
            dat[node] += (r - l + 1) * val;
            return;
        }
        else{
        
         		//修改值时，需要将可能的高层lazy标记下放
          	//使的下方的小区间的值为真实的值，最后累加才会正确
            push_down(node, l, r);
          
            int mid = (l + r) >> 1;
          	//二分去看区间[a,b]和mid的关系
          	//如果a <= mid，那就意味着[a,b]区间在区间[l,mid]中有需要修改的值
          	//那么就需要递归的到[l,mid]区间中去修改
          	//此时节点到左孩子节点
            if(a <= mid)
                update_range(a, b, val, l, mid, node << 1);
          
          	//如果b > mid，那就意味着[a,b]区间在区间[mid + 1,r]中有需要修改的值
          	//那么就需要递归的到[mid + 1,r]区间中去修改
          	//此时节点到右孩子节点
            if(b > mid)
                update_range(a, b, val, mid + 1, r, node << 1 | 1);
          
            dat[node] = dat[node << 1] + dat[node << 1 | 1];	//最后回溯，修改父节点的值
        }
    }
    
    int main()
    {
        
      	//n个数，m次查询
        int n,m;
        scanf("%d %d",&n,&m);
      	
      	//建树
        build(1, 1, n);
        
        for(int i = 0; i < m; i++){
        
            int k;
            int x,y,z;
            cin >> k;
          	//1为单点更新，2为区间查询，3为区间更新
            if(k == 1){
        
              	//在x的位置加上y
                cin >> x >> y;
                update(y, x, 1, n, 1);
            }
            else if(k == 2){
        
              	//查询区间[x,y]
                cin >> x >> y;
                printf("%d\n", query_range(x, y, 1, n, 1));
            }
            else{
        
              	//给区间[x,y]同时加上z
                cin >> x >> y >> z;
                update_range(x, y, z, 1, n, 1);
            }
        }
        
        return 0;
    }