平衡树,AC但疑惑

P3372 【模板】线段树 1

Bodhi @ 2022-12-25 22:55:52

参考的代码

原先没在我的代码中加“org”这个变量(也就是参考的代码中的“val”),结果加上就能过,有大佬能解释一下吗

#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> rbt;

using ll = long long;
const int R = 1e5 + 10;
struct Node
{
    int l, r, size, tag;
    ll val, key, org;
} tree[R];
int tot, root;
mt19937 rd;
int crt(ll val)
{
    tree[++tot].size = 1;
    tree[tot].key = rd();
    tree[tot].val = tree[tot].org = val; //在这里用到
    return tot;
}
void pushdown(int k)
{
    if (tree[k].tag != LLONG_MIN)
    {
        tree[k].val += ll(tree[k].tag) * ll(tree[k].size);
        tree[k].org += tree[k].tag; //这里用到
        if (tree[k].l)
            tree[tree[k].l].tag += tree[k].tag;
        if (tree[k].r)
            tree[tree[k].r].tag += tree[k].tag;
        tree[k].tag = 0;
    }
}
void pushup(int k)
{
    pushdown(tree[k].l);
    pushdown(tree[k].r);
    tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + 1;
    tree[k].val = tree[tree[k].l].val + tree[tree[k].r].val + tree[k].org; //这里用到,也就以上这3处了
}
void split(int k, int sz, int &x, int &y)
{
    if (k == 0)
    {
        x = y = 0;
        return;
    }
    pushdown(k);
    if (tree[tree[k].l].size + 1 <= sz)
    {
        x = k;
        split(tree[k].r, sz - (tree[tree[k].l].size + 1), tree[k].r, y);
    }
    else
    {
        y = k;
        split(tree[k].l, sz, x, tree[k].l);
    }
    pushup(k);
}
int merge(int x, int y)
{
    if (x == 0 || y == 0)
        return x + y;
    if (tree[x].key < tree[y].key)
    {
        pushdown(x);
        tree[x].r = merge(tree[x].r, y);
        pushup(x);
        return x;
    }
    else
    {
        pushdown(y);
        tree[y].l = merge(x, tree[y].l);
        pushup(y);
        return y;
    }
}
void update(int l, int r, int val)
{
    int x, y, z;
    split(root, l - 1, x, y);
    split(y, r - l + 1, y, z);
    tree[y].tag += val;
    root = merge(merge(x, y), z);
}
ll query(int l, int r)
{
    int x, y, z;
    split(root, l - 1, x, y);
    split(y, r - l + 1, y, z);
    pushdown(y);
    ll res = tree[y].val;
    root = merge(merge(x, y), z);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, x, y, k;
    char t;
    cin >> n >> m;
    int j;
    for (j = 1; j <= n; ++j)
    {
        cin >> x;
        root = merge(root, crt(x));
    }
    for (j = 1; j <= m; ++j)
    {
        cin >> t;
        if (t == '1')
        {
            cin >> x >> y >> k;
            update(x, y, k);
        }
        else
        {
            cin >> x >> y;
            cout << query(x, y) << '\n';
        }
    }
    return 0;
}

by whhsteven @ 2022-12-26 02:14:13

这个应该表示的是这个结点上的值吧。


by whhsteven @ 2022-12-26 02:15:47

看起来你的 val 表示的是子树和,那更新子树和时要用到这个结点上的具体值吧。


by 5k_sync_closer @ 2022-12-26 06:48:15

@Bodhi org 是单点点权,val 是子树点权和


by huangkx @ 2022-12-26 07:41:36

@Bodhi 平衡树和线段树维护区间的不同点就在于平衡树的权值不仅在子树上,还在当前的结点上。org 维护的是每个结点自身的权值,而 val 维护的是每个结点的子树的权值,不包含这个结点自身。


by Bodhi @ 2022-12-28 08:40:05

@huangkx 但是我看在pushup的时候这个点的和也是加上了这个点的org的,这又是为什么呢


by huangkx @ 2022-12-28 17:28:43

@Bodhi 哦,那就是您的 val 维护的是这个子树的权值和(包括这个结点),但是同时还要用 org 来维护这个结点的权值。抱歉我之前看错了qwq


|