本文共 2889 字，大约阅读时间需要 9 分钟。

区间更新线段树模板题

这道题是关于区间更新的线段树实现，采用了懒标记的方法来处理区间更新操作。虽然这道题中并没有直接用到降维的方法，但仍然值得学习和记录。

代码概述

以下是实现区间更新线段树的代码，主要包含三个部分：初始化、区间更新和区间查询。

头文件包含

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
         
        
       
      
     
    
   

常用类型定义

typedef long long ll;const int maxn = 1e5 + 10;inline int getid(int x, int y) { return x + y | (y != x); }

数组声明

ll rm[maxn << 1];ll col[maxn << 1];

函数定义

void pushup(int l, int r, int rt) {    rm[rt] = rm[ls] + rm[rs];}void pushdown(int l, int r, int rt, int k) {    if (col[rt]) {        col[ls] += col[rt];        col[rs] += col[rt];        rm[ls] += col[rt] * (k - (k > 1));        rm[rs] += col[rt] * (k > 1);        col[rt] = 0;    }}void build(int l, int r, int rt) {    if (l == r) {        scanf("%lld", &rm[rt]);        return;    }    int m = l + r >> 1;    build(lson);    build(rson);    pushup(l, r, rt);}void update(int L, int R, int c, int l, int r, int rt) {    if (L <= l && r <= R) {        col[rt] += c;        rm[rt] += c * (r - l + 1);        return;    }    pushdown(l, r, rt, r - l + 1);    int m = l + r >> 1;    if (L <= m) {        update(L, R, c, lson);    }    if (R > m) {        update(L, R, c, rson);    }    pushup(l, r, rt);}ll query(int L, int R, int l, int r, int rt) {    if (L <= l && r <= R) {        return rm[rt];    }    pushdown(l, r, rt, r - l + 1);    int m = l + r >> 1;    ll ret = 0;    if (L <= m) {        ret += query(L, R, lson);    }    if (R > m) {        ret += query(L, R, rson);    }    return ret;}

代码解释

1. 头文件包含

该代码包含了常用的一些头文件，包括输入输出、算法、数学、字符串等，确保了程序的正常编译和运行。

2. 常用类型定义

• typedef long long ll; 定义了长整数类型 ll。
• const int maxn = 1e5 + 10; 定义了线段树的最大节点数。
• inline int getid(int x, int y) 用于获取区间的子节点索引。

3. 数组声明

• ll rm[maxn << 1]; 用于存储线段树节点的值。
• ll col[maxn << 1]; 用于存储懒标记值。

4. 函数定义

4.1 void pushup(int l, int r, int rt)

这个函数用于合并左右子节点的值，更新当前节点的值。

4.2 void pushdown(int l, int r, int rt, int k)

这个函数用于将懒标记从当前节点分发到左右子节点。

4.3 void build(int l, int r, int rt)

这个函数用于初始化线段树，递归地构建线段树的节点，并从 rm 数组读取初始值。

4.4 void update(int L, int R, int c, int l, int r, int rt)

这个函数用于区间更新。它检查当前节点是否完全包含在目标区间内，否则分割处理，并调用 pushdown 函数推送懒标记。

4.5 ll query(int L, int R, int l, int r, int rt)

这个函数用于区间查询。它检查当前节点是否完全包含在目标区间内，否则分割处理，并递归查询左右子节点。

5. 使用方法

5.1 初始化

调用 build 函数初始化线段树：

build(0, maxn - 1, maxn);

5.2 区间更新

调用 update 函数进行区间更新：

update(L, R, c, 0, maxn - 1, maxn);

5.3 区间查询

调用 query 函数进行区间查询：

ll result = query(L, R, 0, maxn - 1, maxn);

6. 优化建议

• 懒标记处理：通过懒标记技术，减少了递归深度，提高了效率。
• 区间更新：在 update 函数中，使用了 pushdown 技巧，确保了懒标记的正确传递。
• 递归优化：在 build 和 query 函数中，通过合理分割区间，减少了递归深度，提高了性能。

总结

这篇文章介绍了一个简洁高效的区间更新线段树实现，通过懒标记技术，有效地处理了区间更新和查询操作。虽然这道题中暂时不需要降维技术，但理解这种实现方式对于掌握线段树的核心算法非常有帮助。

转载地址：http://lfxfk.baihongyu.com/