首页 > 其他分享 >Scape - Goat Tree

Scape - Goat Tree

时间：2023-01-29 22:46:11浏览次数：45  
标签：sz return val int Tree tr son Scape Goat

目录

Scape - Goat Tree

主打的就是一个定期重构，惰性删除。

通过一个节点的平衡性从而判断是否重构整棵树，我想那一个节点就是 雪风大人 替罪羊吧。

该文的替罪羊树十分暴力，甚至不清楚时间复杂度对不对。

来，一键护航。

Basis

Definition

struct Yukikaze
{
    struct ScapeGoatTree
    {
        int son[2]; // 左右子节点编号。0表示左子节点，1表示右子节点。
        int val; // 该点权值
        int sz; // 子树大小（包含重复数字）
        int cnt; // 相同权值的数的个数
    }tr[N];
    int root, tot;
    int cur[N], curcnt; // 重构数组
}

Push up

void pushup(int p)
{
    tr[p].sz = tr[tr[p].son[0]].sz + tr[tr[p].son[1]].sz + tr[p].cnt;
}

Check

任意一边的子树过大了，就暴力重构。

bool is_bad(int u)
{
    if(1.0 * tr[u].sz * Alpha < 1.0 * tr[tr[u].son[0]].sz)
        return true;
    if(1.0 * tr[u].sz * Alpha < 1.0 * tr[tr[u].son[1]].sz)
        return true;
    return false;
}

Mid-travel

void midtravel(int u) // 中序遍历，存需要重构的点
{
    if(!u) return;
    midtravel(tr[u].son[0]);
    if(tr[u].cnt) cur[++curcnt] = u; 
    // tr[u].cnt == 0 就不用被建到新树上了。这里是真正意义地被删除出平衡树。
    midtravel(tr[u].son[1]);
}

中序遍历还有个很实用的作用是 debug。

void print(int u)
{
    if(!u) return;
    print(tr[u].son[0]);
    if(tr[u].cnt) printf("%d %d %d %d\n", u, tr[u].val, tr[u].son[0], tr[u].son[1]);
    print(tr[u].son[1]);
}

build & rebuild

int build(int l, int r)
{
    if(l > r) return 0; // 注意不能写等号，否则叶节点无法被加入到新树中
    int mid = l + (r - l) / 2;
    // 以下注意 cur[mid] 的地方不要写成 mid
    tr[cur[mid]].son[0] = build(l ,mid - 1);
    tr[cur[mid]].son[1] = build(mid + 1, r);
    pushup(cur[mid]);
    return cur[mid];
}

void rebuild(int &u)
{
    curcnt = 0;
    midtravel(u);
    u = build(1, curcnt);
}

Insert

void insert(int &u, int x)
{
    if(!u)
    {
        u = ++tot;
        tr[u].val = x;
        tr[u].son[0] = tr[u].son[1] = 0;
        tr[u].sz = tr[u].cnt = 1;
        return;
    }
    if(x == tr[u].val) tr[u].cnt++;
    else if(x < tr[u].val) 
        insert(tr[u].son[0], x);
    else if(x > tr[u].val)
        insert(tr[u].son[1], x);
    pushup(u);
    if(is_bad(u))
        rebuild(u);
    return;
}

Remove

void remove(int &u, int x)
{
    if(!u) return;
    if(x == tr[u].val)
    {
        if(tr[u].cnt)
            tr[u].cnt--;
    }
    else if(x < tr[u].val)
        remove(tr[u].son[0], x);
    else if(x > tr[u].val)
        remove(tr[u].son[1], x);
    pushup(u);
    if(is_bad(u))
        rebuild(u);
    return;
}

Get rank by value

int get_rank_by_val(int u, int x)
{
    if(!u) return 1; // 注意返回 "+1"
    if(x == tr[u].val && tr[u].cnt) // 注意判断该点是否已经被惰性删除了
        return tr[tr[u].son[0]].sz + 1;
    if(x < tr[u].val)
        return get_rank_by_val(tr[u].son[0], x);
    return tr[tr[u].son[0]].sz + tr[u].cnt + get_rank_by_val(tr[u].son[1], x);
}

Get value by rank

int get_val_by_rank(int u, int x)
{
    if(!u) return 0;
    if(x > tr[tr[u].son[0]].sz && x <= tr[tr[u].son[0]].sz + tr[u].cnt) // && tr[u].cnt
        return tr[u].val; // 如果 tr[u].cnt == 0，则这个 if 一定不成立，因此可以不用判断
    if(x <= tr[tr[u].son[0]].sz)
        return get_val_by_rank(tr[u].son[0], x);
    return get_val_by_rank(tr[u].son[1], x - tr[tr[u].son[0]].sz - tr[u].cnt);
}

Get last & Get next

int get_lstval(int x)
{
    int rank = get_rank_by_val(root, x) - 1; 
    // 这里并不是排名的真正定义，只是为了找前驱的值而非前驱的排名
    return get_val_by_rank(root, rank);
}
int get_nxtval(int x)
{
    int rank = get_rank_by_val(root, x + 1);
    // 这个是排名的真正定义，且通过排名找到了后继的值
    return get_val_by_rank(root, rank);
}

注意有这样一种写法是 错误 的：

    int get_lstval(int x)
    {
        int u = root, res = -INF;
        while(u)
        {
            if(tr[u].val < x && tr[u].cnt)
                res = tr[u].val;
            u = tr[u].son[tr[u].val < x];
        }
        return res;
    }
    int get_nxtval(int x)
    {
        int u = root, res = INF;
        while(u)
        {
            if(tr[u].val > x && tr[u].cnt)
                res = tr[u].val;
            u = tr[u].son[tr[u].val <= x];
        }
        return res;
    }

原因是从被惰性删除但还没有完全删除的节点往下跳，可能出现问题。

比如：

现在 get_lstval(x)，1, 2 号节点被删除。此时如果 5 号节点的值大于 6 号节点的值，则查询结果就出错了。

上述算法会从 1 往左跳，查询到 6 号节点并返回 6 号节点的值，但答案应为 5 号节点的值。

查询后继同样会遇到类似的问题。

Final Code

#include<bits/stdc++.h>
using namespace std;
const double Alpha = 0.75;
const int N = 2e6 + 5;
const int INF = INT_MAX;
struct Yukikaze
{
    struct ScapeGoatTree
    {
        int son[2];
        int val;
        int sz, cnt;
    }tr[N];
    int root, tot;
    int cur[N], curcnt;
    void pushup(int p)
    {
        tr[p].sz = tr[tr[p].son[0]].sz + tr[tr[p].son[1]].sz + tr[p].cnt;
    }
    bool is_bad(int u)
    {
        if(1.0 * tr[u].sz * Alpha < 1.0 * tr[tr[u].son[0]].sz)
            return true;
        if(1.0 * tr[u].sz * Alpha < 1.0 * tr[tr[u].son[1]].sz)
            return true;
        return false;
    }
    void midtravel(int u)
    {
        if(!u) return;
        midtravel(tr[u].son[0]);
        if(tr[u].cnt) cur[++curcnt] = u;
        midtravel(tr[u].son[1]);
    }
    void print(int u)
    {
        if(!u) return;
        print(tr[u].son[0]);
        if(tr[u].cnt) printf("%d %d %d %d\n", u, tr[u].val, tr[u].son[0], tr[u].son[1]);
        print(tr[u].son[1]);
    }
    int build(int l, int r)
    {
        if(l > r) return 0;
        int mid = l + (r - l) / 2;
        tr[cur[mid]].son[0] = build(l ,mid - 1);
        tr[cur[mid]].son[1] = build(mid + 1, r);
        pushup(cur[mid]);
        return cur[mid];
    }
    void rebuild(int &u)
    {
        curcnt = 0;
        midtravel(u);
        u = build(1, curcnt);
    }
    void insert(int &u, int x)
    {
        if(!u)
        {
            u = ++tot;
            tr[u].val = x;
            tr[u].son[0] = tr[u].son[1] = 0;
            tr[u].sz = tr[u].cnt = 1;
            return;
        }
        if(x == tr[u].val) tr[u].cnt++;
        else if(x < tr[u].val) 
            insert(tr[u].son[0], x);
        else if(x > tr[u].val)
            insert(tr[u].son[1], x);
        pushup(u);
        if(is_bad(u))
            rebuild(u);
        return;
    }
    void remove(int &u, int x)
    {
        if(!u) return;
        if(x == tr[u].val)
        {
            if(tr[u].cnt)
                tr[u].cnt--;
        }
        else if(x < tr[u].val)
            remove(tr[u].son[0], x);
        else if(x > tr[u].val)
            remove(tr[u].son[1], x);
        pushup(u);
        if(is_bad(u))
            rebuild(u);
        return;
    }
    int get_val_by_rank(int u, int x)
    {
        if(!u) return 0;
        if(x > tr[tr[u].son[0]].sz && x <= tr[tr[u].son[0]].sz + tr[u].cnt) // && tr[u].cnt
            return tr[u].val;
        if(x <= tr[tr[u].son[0]].sz)
            return get_val_by_rank(tr[u].son[0], x);
        return get_val_by_rank(tr[u].son[1], x - tr[tr[u].son[0]].sz - tr[u].cnt);
    }
    int get_rank_by_val(int u, int x)
    {
        if(!u) return 1;
        if(x == tr[u].val && tr[u].cnt)
            return tr[tr[u].son[0]].sz + 1;
        if(x < tr[u].val)
            return get_rank_by_val(tr[u].son[0], x);
        return tr[tr[u].son[0]].sz + tr[u].cnt + get_rank_by_val(tr[u].son[1], x);
    }
    int get_lstval(int x)
    {
        int rank = get_rank_by_val(root, x) - 1;
        return get_val_by_rank(root, rank);
    }
    int get_nxtval(int x)
    {
        int rank = get_rank_by_val(root, x + 1);
        return get_val_by_rank(root, rank);
    }
}swd; // snow wind. - destroyer!!!
int n, Q, lastans, ans;
int main()
{
    scanf("%d %d", &n, &Q);
    for(int i = 1; i <= n; ++i)
    {
        int x; scanf("%d", &x);
        swd.insert(swd.root, x);
    }
    swd.insert(swd.root, INF);
    swd.insert(swd.root, -INF);
    while(Q--)
    {
        int op, x;
        scanf("%d %d", &op, &x);
        x ^= lastans;
        if(op == 1) swd.insert(swd.root, x);
        if(op == 2) swd.remove(swd.root, x);
        if(op == 3) lastans = swd.get_rank_by_val(swd.root, x) - 1;
        if(op == 4) lastans = swd.get_val_by_rank(swd.root, x + 1);
        if(op == 5) lastans = swd.get_lstval(x);
        if(op == 6) lastans = swd.get_nxtval(x);
        if(op > 2) ans ^= lastans;
        // swd.print(swd.root); puts("");
    }
    printf("%d\n", ans);
    return 0;
}

标签：sz,return,val,int,Tree,tr,son,Scape,Goat
From： https://www.cnblogs.com/Schucking-Sattin/p/17074016.html

相关文章

  • 题解 CF277E【Binary Tree on Plane】
    费用流。可以将原问题转化为类似于匹配的问题，只不过这种匹配并不是一对一的。具体地，将每个点\(u\)拆成两个点\(u_\text{fa},u_\text{son}\)，设源点为\(s\)、汇点为\(t......
  • Potree 004 点云点大小形状设置
    点云数据就是靠海量的点显示来模拟真实世界的。点大小设置就比较重要，例如如果数据稀疏，点显示的时候，可以设置稍微大一些。如果点数据比较密集，则可以显示小一些。在Potree中......
  • 【模板】ODT | Old Driver Tree | 珂朵莉树
    postedon2021-04-0220:38:49|under学术|source这个东西本身不常用，但是这个维护连续段的写法很常用。标签：暴力、数据结构、std::set#include<set>template<cla......
  • hexo-theme-tree
    Hexo主题Tree一个简洁的主题，主要功能是“树状导航”+“树状目录”，可选配“评论”和“阅读量”功能，支持基于搜索引擎的全站搜索。通过fancybox支持图片点击放大。......
  • python-Couldn‘t find a tree builder with the features you requested: lxml
    执行BeautifulSoup(content,features='lxml')时报错，按照网上的方法安装lxml、重新安装lxml、安装指定版本lxml，都无效。最后发现只是PyCharm设置中project的pyth......
  • 二叉树的实现-BSTree
    二叉树的实现-BSTree一、树和二叉树1-1树的定义翻译过来就是：树是由结点构成的，结点可以有也可以没有。若有结点，则肯定只有一个根结点。树是一种递归结构，俗称“套娃”......
  • 【Winform】TreeView使用汇总
    1、拖拽节点到另一个容器Panel中TreeView控件需要监听：（1）ItemDrag事件(当用户开始拖动节点时发生)。对于Panel控件：（1）开启Panel的AlowDrop属性设置为true表示允许进行拖入操......
  • 「解题报告」ARC138F KD Tree
    好题！感觉比那些写出DP然后无脑上GF数学方法硬推的题有价值。首先有个朴素的想法：设\(f_{l,r,u,d}\)表示这个矩形的方案数，那么枚举分界点转移。引用大佬的话：直......
  • 浅谈树上启发式合并（Dsu on tree）
    树上启发式合并树上启发式合并（Dsuontree），是一个解决树上离线问题的有力算法，一般的复杂度是\(\mathcalO(n\logn)\)（假定转移可以\(\mathcalO(1)\)解决），时间复杂度相比......
  • RTree源代码——C语言实现
    RTree源代码——C语言实现cheungmine一、什么是RTree“R树是B树向多维空间发展的另一种形式，它将空间对象按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99