为此，我们给节点添加一个「懒惰标记」，给更新区间的对应节点添加一个懒惰标记，表示该节点所有对应的孩子节点都应该有此次更新，当向孩子节点遍历的时候会把「懒惰标记」下推给孩子节点，如果节点不存在最优孩子节点时需要创建左右孩子节点，最终我们修改 Node 的数据结构：
class Node {int val; // 当前节点值int lazy;// 添加的懒惰标记Node* left, right; // 左右孩子节点Node(int a=0): val(a), left(nullptr), right(nullptr) {};~Node() {delete left;delete right;}}
『下推懒惰标记』函数：
// leftNum 和 rightNum 表示左右孩子区间的叶子节点数量void pushDown(Node* node, int leftNum, int rightNum) {if (node->left == nullptr) node->left = new Node();if (node->right == nullptr) node->right = new Node();// 没有标记直接返回if (node->lazy == 0) return;// 如果是「加减」更新操作就需要使用：标记值 * 子树所有叶子节点数量node->left->val += node->lazy * leftNum;node->right->val += node->lazy * rightNum;// 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖node->left->lazy += node->lazy;node->right->lazy += node->lazy;// 取消当前节点的标记node->lazy = 0;}
「更新最终函数」：
// 在 start...end 范围内更新 l...r 区间中的每个元素，都加 valvoid update(Node* node, int start, int end, int l, int r, int val) {// 找到满足要求的区间if (l <= start && end <= r) {// 区间节点加上子树所有叶子节点node->val += (end - start + 1) * val;// 累计添加懒惰标记node->lazy += val;return ;}int mid = (start + end) / 2;// 下推标记，mid - start + 1 表示左孩子区间叶子节点数量，end - mid 表示右孩子区间叶子节点数量pushDown(node, mid - start + 1, end - mid);if (l <= mid) update(node->left, start, mid, l, r, val);if (r > mid) update(node->right, mid + 1, end, l, r, val);// 向上更新pushUp(node);}
查询线段树：查询某一个区间如 [2, 4] 的结果（图中红色标记）并返回
// 在区间 [start, end] 中查询区间 [l, r] 的结果，注意 [l, r] 保持不变int query(Node* node, int start, int end, int l , int r) {// 区间 [l ,r] 完全包含区间 [start, end]// 例如：[2, 4] = [2, 2] + [3, 4]，当 [start, end] = [2, 2] 或者 [start, end] = [3, 4]，直接返回if (l <= start && end <= r) {return node->val;}// 把当前区间 [start, end] 均分得到左右孩子的区间范围// node 左孩子区间 [start, mid]// node 左孩子区间 [mid + 1, end]int mid = (start + end) / 2;int ans = 0;pushDown(node, mid - start + 1, end - mid);if (l <= mid) {ans += query(node, start, mid, l, r);}if (r > mid) {ans += query(node->right, mid + 1, end, l, r);}return ans;}
2. 完整模板
基于求「区间和」以及对区间进行「加减」的更新操作的常规模板
// 线段树代码#include #include using namespace std;// node_idx 为线段树下标，从1开始取void build_tree(vector& arr, vector& tree, int start, int end, int node_idx){//递归的出口，也就是到了叶子节点if(start == end) {tree[node_idx] = arr[start];} else {//找到左子树的节点(2*node_idx)//找到右子树的节点(2*node_idx+1)int left_node = 2*node_idx, right_node = 2*node_idx + 1;int mid = (start + end) / 2;//将树进行分割，然后左右递归建树build_tree(arr, tree, start, mid, left_node);build_tree(arr, tree, mid+1, end, right_node);tree[node_idx] = tree[left_node] + tree[right_node];}}// 查询 [l, r] 的区间和，node_idx 从1开始int query(vector& arr, vector& tree, int start, int end, int l, int r, int node_idx){//情况一if(l > end || r