附例题【LeetCode】一文吃透线段树( 三 ) _区间

< start) {return 0;} else if (l <= start && end <= r) { //情况二return tree[node_idx];} 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;//将树进行分割，然后左右递归查询int left_sum = query(arr, tree, start, mid, l, r, left_node);int right_sum = query(arr, tree, mid+1, end, l, r, right_node);return left_sum + right_sum;}}// 更新指定下标 update_idx 的元素，node_idx 从1开始取void update(vector& arr, vector& tree, int start, int end, int node_idx, int update_idx, int val){//递归的出口，也就是到了叶子节点, 更新其值if(start == end) {tree[node_idx] = arr[start] = val;} 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;//如果要更新节点在右边if(update_idx > mid) {update(arr, tree, mid+1, end, right_node, update_idx, val);} else { //要更新节点在左边update(arr, tree, start, mid, left_node, update_idx, val);}//要注意更新当前节点！！！！！！tree[node_idx] = tree[left_node] + tree[right_node];}}int main(){vector arr = {93, 90, 50, 50, 1};int n = arr.size();vector tree(4*n);build_tree(arr, tree, 0, n-1, 1);cout << "更新前的树:";for (auto& x : tree) cout << x << " ";cout << endl;//更新 idx = 4的元素值为 2update(arr, tree, 0, n-1, 1, 4, 2);cout << "更新后的树:";for (auto& x : tree) cout << x << " ";cout << endl;cout << "查询区间[2,4]的和为：" << query(arr, tree, 0, n-1, 2, 4, 1) << endl;return 0;}
基于求「区间和」以及对区间进行「加减」的更新操作，且为「动态开点」的模板
struct Node {int lazy;int val;Node* left;Node* right;Node(int a = 0): val(a), lazy(0), left(nullptr), right(nullptr) {}; };class SegmentTree {private:Node* root;public:SegmentTree() {root = new Node();}// 更新 [l, r] 区间里面元素void 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;// 下推懒惰标记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);}int query(Node* node, int start, int end, int l, int r) {if (l <= start && end <= r) return node->val;int mid = (start + end) / 2;int ans = 0;pushDown(node, mid - start + 1, end - mid);if (l <= mid) ans += query(node->left, start, mid, l, r);if (r > mid) ans += query(node->right, mid + 1, end, l, r);return ans;}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;}// 这里如果不是维护区间和需要注意改变void pushUp(Node* node) {node->val = node->left->val + node->right->val;}};
3. 常见题型题目说明题解
729. 我的日程安排表 I
维护区间最值并对区间进行加减更新，暴力维护，差分数组
解
731. 我的日程安排表 II
维护区间最值并对区间进行加减更新，暴力维护，差分数组
解
732. 我的日程安排表 III
维护区间最值并对区间进行加减更新，差分数组
解
307. 区域和检索 - 数组可修改
维护区间和并对区间进行覆盖更新，参考题解的第二份cpp代码
解
933. 最近的请求次数
维护区间和并对区间进行加减更新，直接队列就可以
解
注意：对于题目最近的请求次数和区域和检索 - 数组可修改可以「不用??左右孩子区间叶子节点的数量」

附例题 【LeetCode】一文吃透线段树( 三 )

附例题【LeetCode】一文吃透线段树( 三 )