1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <iostream>
using namespace std;
class Node {
private:
Node *left, *right;
int val, add;
public:
void update(Node* cur, int start, int end, int l, int r, int val) {
if (l <= start && end <= r) {
cur->val += (end - start + 1) * val;
cur->add += val;
return ;
}
int mid = (start + end) >> 1;
pushDown(cur, mid - start + 1, end - mid);
if (l <= mid) update(cur->left, start, mid, l, r, val);
if (r > mid) update(cur->right, mid + 1, end, l, r, val);
pushUp(cur);
}
int query(Node* cur, int start, int end, int l, int r) {
if (l <= start && end <= r) return cur->val;
int mid = (start + end) >> 1, ans = 0;
pushDown(cur, mid - start + 1, end - mid);
if (l <= mid) ans += query(cur->left, start, mid, l, r);
if (r > mid) ans += query(cur->right, mid + 1, end, l, r);
return ans;
}
void pushUp(Node* cur) {
cur->val = cur->left->val + cur->right->val;
}
void pushDown(Node* cur, int leftNum, int rightNum) {
if (cur->left == nullptr) cur->left = new Node();
if (cur->right == nullptr) cur->right = new Node();
if (cur->add == 0) return ;
cur->left->val += cur->add * leftNum;
cur->right->val += cur->add * rightNum;
// 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
cur->left->add += cur->add;
cur->right->add += cur->add;
cur->add = 0;
}
};
int main() {
Node* root = new Node();
int N = 1e5;
root->update(root, 0, N, 1, 115, 3);
root->update(root, 0, N, 12, 55, 68);
root->update(root, 0, N, 37, 90, 7);
root->update(root, 0, N, 34, 60, 5);
root->update(root, 0, N, 12, 33, 3);
root->update(root, 0, N, 23, 56, 6);
root->update(root, 0, N, 31, 134, 16);
root->update(root, 0, N, 62, 156, 47);
root->update(root, 0, N, 1, 24, 52);
for (int i = 0; i <= 200; ++ i) {
cout << root->query(root, 0, N, i, i) << ' ';
}
return 0;
}
|
