唔，一个百思不得其解的 树状树状题目相关的问题
这里s % x != 0。那后面应该没有用了吧？为什么= nullptr; 后原来对的会变成错的？加上前
加上后
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 5e5 + 5;
struct Node {
int l, r;
long long val;
Node* left, * right;
Node(long long val, int l, int r) : val(val), l(l), r(r), left(nullptr), right(nullptr) {}
};
int n, m;
long long s;
Node* head = nullptr;
Node* f = { nullptr };
long long get_val(Node* node) {
if (node == nullptr)
return 0;
return node->val;
}
//查询l到r的和
long long query(Node* node, int l, int r) {
if (node == nullptr)
return 0;
if (l == node->l && r == node->r)
return node->val;
int mid = node->l + (node->r - node->l >> 1);
if (r <= mid)
return query(node->left, l, r);
else if (mid < l)
return query(node->right, l, r);
else
return query(node->left, l, mid) + query(node->right, mid + 1, r);
}
//修改v处的值为x
void modify(Node*& node, int l, int r, int v, long long x) {
if (node == nullptr)
node = new Node(0, l, r);
if (node->l == node->r) {
node->val = x;
}
else {
int mid = node->l + (node->r - node->l >> 1);
if (v > mid)
modify(node->right, mid + 1, r, v, x);
else
modify(node->left, l, mid, v, x);
node->val = get_val(node->left) + get_val(node->right);
}
}
//根据s数组构建一颗树
void create(Node*& node, int l, int r) {
if (node == nullptr) {
node = new Node(0, l, r);
}
if (l == r) {
node->val = s;
}
else {
int mid = node->l + (node->r - node->l >> 1);
create(node->left, l, mid);
create(node->right, mid + 1, r);
node->val = get_val(node->left) + get_val(node->right);
}
}
//遍历l~r中的数，将可以除的除了,不能除的删除了
void update(Node*& node, int l, int r, int x) {
if (node == nullptr) return;
if (l == r) {
if (s % x == 0) {
s /= x;
modify(head, 1, n, l, s);
}
else {
node = nullptr; //这里不加，大部分超时，加了，答案错误
}
}
else {
int mid = node->l + (node->r - node->l >> 1);
if (r <= mid)
update(node->left, l, r, x);
else if (mid < l)
update(node->right, l, r, x);
else
update(node->left, l, mid, x), update(node->right, mid + 1, r, x);
node->val = get_val(node->left) + get_val(node->right);
if (node->val == 0) {
node = nullptr;
}
}
}
int main() {
ios_base::sync_with_stdio(0); //把cin和scnf分割开,加快速度
cin.tie(0); //解除cin与cout的绑定
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 1; j * j <= s; j++) {
if (s % j == 0) {
modify(f, 1, n, i, 1);
if (j * j != s)
modify(f / j], 1, n, i, 1);
}
}
}
create(head, 1, n);
for (int i = 0; i < m; i++) {
int num, l, r, x;
cin >> num >> l >> r;
if (num == 1) {
cin >> x;
if (x == 1) continue;
update(f, l, r, x);
}
else {
cout << query(head, l, r) << '\n';
}
}
return 0;
} s % x != 0表示该位置的数不能整除x,所以后续的查询和修改都不会用到这个节点了。
但是如果直接node = nullptr删除这个节点,之前通过这个节点存储的信息也会丢失。
举个例子:
原数组:1 2 3 4
构建的线段树:
1-4 (1+2+3+4=10)
/ \
1-2 (1+2=3) 3-4 (3+4=7)
现在有修改操作:2-3 3 (把区间2-3的数除以3)
线段树变成:
1-4 (1+1+1+4=7)
/ \
1-2 (1+1=2) 3-4 (3+4=7)
此时再有查询操作1-4,应该返回7。
而如果直接删除节点3-4,则:
1-4
/
1-2 (1+1=2)
则查询1-4会返回2,与预期不符。
所以,采用if检查判断是否需要删除节点,如果需要删除再设置为nullptr的做法是正确的。既避免了直接删除节点导致信息丢失的情况,也删除了不再需要的节点。
希望通过这个例子能够理解为什么要加if判断,以及不加if判断会产生什么错误。如果还有不清楚的地方,欢迎再提问。 update() 的 if 条件错了，应该是 node->l == node->r
不然修改的区间的长度为 1 的话就直接判断能不能除了
页:
[1]