[已解决]唔，一个百思不得其解的 树状树状题目相关的问题

御坂19090

这里s[l] % x != 0。那后面应该没有用了吧？为什么= nullptr;   后原来对的会变成错的？
加上前
加上后

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. const int MAX = 5e5 + 5;
   
7. 
   
8. struct Node {
   
9.     int l, r;
   
10.     long long val;
    
11.     Node* left, * right;
    
12. 
    
13.     Node(long long val, int l, int r) : val(val), l(l), r(r), left(nullptr), right(nullptr) {}
    
14. };
    
15. 
    
16. int n, m;
    
17. long long s[MAX];
    
18. Node* head = nullptr;
    
19. Node* f[MAX] = { nullptr };
    
20. 
    
21. long long get_val(Node* node) {
    
22.     if (node == nullptr)
    
23.         return 0;
    
24.     return node->val;
    
25. }
    
26. 
    
27. //查询l到r的和
    
28. long long query(Node* node, int l, int r) {
    
29.     if (node == nullptr)
    
30.         return 0;
    
31.     if (l == node->l && r == node->r)
    
32.         return node->val;
    
33. 
    
34.     int mid = node->l + (node->r - node->l >> 1);
    
35.     if (r <= mid)
    
36.         return query(node->left, l, r);
    
37.     else if (mid < l)
    
38.         return query(node->right, l, r);
    
39.     else
    
40.         return query(node->left, l, mid) + query(node->right, mid + 1, r);
    
41. }
    
42. 
    
43. //修改v处的值为x
    
44. void modify(Node*& node, int l, int r, int v, long long x) {
    
45.     if (node == nullptr)
    
46.         node = new Node(0, l, r);
    
47.     if (node->l == node->r) {
    
48.         node->val = x;
    
49.     }
    
50.     else {
    
51.         int mid = node->l + (node->r - node->l >> 1);
    
52.         if (v > mid)
    
53.             modify(node->right, mid + 1, r, v, x);
    
54.         else
    
55.             modify(node->left, l, mid, v, x);
    
56. 
    
57.         node->val = get_val(node->left) + get_val(node->right);
    
58.     }
    
59. }
    
60. 
    
61. //根据s数组构建一颗树
    
62. void create(Node*& node, int l, int r) {
    
63.     if (node == nullptr) {
    
64.         node = new Node(0, l, r);
    
65.     }
    
66.     if (l == r) {
    
67.         node->val = s[l];
    
68.     }
    
69.     else {
    
70.         int mid = node->l + (node->r - node->l >> 1);
    
71.         create(node->left, l, mid);
    
72.         create(node->right, mid + 1, r);
    
73. 
    
74.         node->val = get_val(node->left) + get_val(node->right);
    
75.     }
    
76. }
    
77. 
    
78. //遍历l~r中的数，将可以除的除了,不能除的删除了
    
79. void update(Node*& node, int l, int r, int x) {
    
80.     if (node == nullptr) return;
    
81. 
    
82.     if (l == r) {
    
83.         if (s[l] % x == 0) {
    
84.             s[l] /= x;
    
85.             modify(head, 1, n, l, s[l]);
    
86.         }
    
87.         else {
    
88.             node = nullptr; //这里不加，大部分超时，加了，答案错误
    
89.         }
    
90.     }
    
91.     else {
    
92.         int mid = node->l + (node->r - node->l >> 1);
    
93.         if (r <= mid)
    
94.             update(node->left, l, r, x);
    
95.         else if (mid < l)
    
96.             update(node->right, l, r, x);
    
97.         else
    
98.             update(node->left, l, mid, x), update(node->right, mid + 1, r, x);
    
99. 
    
100.         node->val = get_val(node->left) + get_val(node->right);
     
101. 
     
102.         if (node->val == 0) {
     
103.             node = nullptr;
     
104.         }
     
105.     }
     
106. }
     
107. 
     
108. int main() {
     
109.     ios_base::sync_with_stdio(0);   //把cin和scnf分割开,加快速度
     
110.     cin.tie(0); //解除cin与cout的绑定
     
111. 
     
112.     cin >> n >> m;
     
113. 
     
114.     for (int i = 1; i <= n; i++) {
     
115.         cin >> s[i];
     
116.         for (int j = 1; j * j <= s[i]; j++) {
     
117.             if (s[i] % j == 0) {
     
118.                 modify(f[j], 1, n, i, 1);
     
119.                 if (j * j != s[i])
     
120.                     modify(f[s[i] / j], 1, n, i, 1);
     
121.             }
     
122.         }
     
123.     }
     
124. 
     
125.     create(head, 1, n);
     
126. 
     
127.     for (int i = 0; i < m; i++) {
     
128.         int num, l, r, x;
     
129.         cin >> num >> l >> r;
     
130.         if (num == 1) {
     
131.             cin >> x;
     
132.             if (x == 1) continue;
     
133.             update(f[x], l, r, x);
     
134.         }
     
135.         else {
     
136.             cout << query(head, l, r) << '\n';
     
137.         }
     
138.     }
     
139. 
     
140.     return 0;
     
141. }

复制代码

最佳答案

月排行榜 / 总排行榜

不二如是

2023-6-12 18:19:40

s[l] % x != 0表示该位置的数不能整除x,所以后续的查询和修改都不会用到这个节点了。

但是如果直接node = nullptr删除这个节点,之前通过这个节点存储的信息也会丢失。

举个例子:
原数组:1 2 3 4
构建的线段树:

1. 1-4 (1+2+3+4=10)
   
2. / \
   
3. 1-2 (1+2=3) 3-4 (3+4=7)

复制代码

现在有修改操作:2-3 3 (把区间2-3的数除以3)
线段树变成:

1. 1-4 (1+1+1+4=7)
   
2. / \
   
3. 1-2 (1+1=2) 3-4 (3+4=7)

复制代码

此时再有查询操作1-4,应该返回7。

而如果直接删除节点3-4,则:

1. 1-4
   
2. /
   
3. 1-2 (1+1=2)

复制代码

则查询1-4会返回2,与预期不符。

所以,采用if检查判断是否需要删除节点,如果需要删除再设置为nullptr的做法是正确的。既避免了直接删除节点导致信息丢失的情况,也删除了不再需要的节点。

希望通过这个例子能够理解为什么要加if判断,以及不加if判断会产生什么错误。如果还有不清楚的地方,欢迎再提问。

跳转到最佳答案楼层

不二如是

s[l] % x != 0表示该位置的数不能整除x,所以后续的查询和修改都不会用到这个节点了。

但是如果直接node = nullptr删除这个节点,之前通过这个节点存储的信息也会丢失。

举个例子:
原数组:1 2 3 4
构建的线段树:

1. 1-4 (1+2+3+4=10)
   
2. / \
   
3. 1-2 (1+2=3) 3-4 (3+4=7)

复制代码

现在有修改操作:2-3 3 (把区间2-3的数除以3)
线段树变成:

1. 1-4 (1+1+1+4=7)
   
2. / \
   
3. 1-2 (1+1=2) 3-4 (3+4=7)

复制代码

此时再有查询操作1-4,应该返回7。

而如果直接删除节点3-4,则:

1. 1-4
   
2. /
   
3. 1-2 (1+1=2)

复制代码

则查询1-4会返回2,与预期不符。

所以,采用if检查判断是否需要删除节点,如果需要删除再设置为nullptr的做法是正确的。既避免了直接删除节点导致信息丢失的情况,也删除了不再需要的节点。

希望通过这个例子能够理解为什么要加if判断,以及不加if判断会产生什么错误。如果还有不清楚的地方,欢迎再提问。

御坂19090

update() 的 if 条件错了，应该是 node->l == node->r
不然修改的区间的长度为 1 的话就直接判断能不能除了