この記事はレジリエントでウェルビーイングなぴょこりんクラスタ Advent Calendar 2024 の為に書いたものです。

はじめに

この記事は前回の続きです。続きものとなりますので、前回の内容は（ここ）から参照してください。
Treap でとけるよって言われた問題、 Treap なしで解けちゃったんだけど、結局 Treap 使ってどう解くの？という話でした。

今回は、この方針を決めるために、 Treap って結局何なのか、を深堀していこうと思います。

Treap とは何なのか

前回でも少し話題にしましたが、 Treap は乱数を用いた平衡二分木です。

二分木・二分探索木のおさらい

Treap について話す前に二分木についておさらいすると、子が二つしかない木構造のことです。

二分木の中でもよく用いられている二分探索木は、
データの大小に応じて小さい値を左、大きい値を右に格納していくことで、
$N$ 個のデータをおよそ $O(log N)$ の深さの二分木に格納することができて、
結果的に挿入・検索・削除等の操作を $O(log N)$ で行うことができる、というものでした。

上のようなイメージ通りの動作をしてくれれば基本的に二分探索木は優秀ですが、
素朴な実装においては
データの挿入順を恣意的な順番にすると、意図せず操作に $O(N)$ の時間がかかってしまうことがあることが問題でした。

平衡二分木と Treap

平衡二分木といった時には、何らかの方法でこういった木の偏りをならすことで、
データの順などによらず、挿入・検索・削除を $O(log N)$ で行えるようにするデータ構造のことを指します。

Treap において木の偏りをならすのはどのように行われているかというと、
データが挿入されるごとに裏データとして乱数を割り当て、乱数の小さい順にデータが挿入されたときと同じような状態に木の形を作っていく、というものです。

データが格納されるごとに乱数の順でデータが挿入されたものと結果が同じようになる、というのは

Step 1 はデータ列 1 が格納された形と一緒
Step 2 はデータ列 [2, 1] が格納された形と一緒
Step 3 はデータ列 [3, 2, 1] が格納された形と一緒
Step 4 はデータ列 [3, 2, 1, 4] が格納された形と一緒
Step 5 はデータ列 [3, 2, 1, 6, 4] が格納された形と一緒
Step 6 はデータ列 [3, 2, 1, 6, 4, 7] が格納された形と一緒

ってことです。 Step 1 では根にあった１が Step 2では葉になってたり、 Step 4では 3の子であった 4 が Step 5 では 6 の子になってる、とかがミソです。

もちろん、乱数の付き方次第ではバランスの悪い木が作れる可能性は存在しますが、少なくとも恣意的なデータの挿入などでバランスを悪くすることは不可能、という点で二分探索木より優れています。

原理はわかったけど、こんなデータ構造って実装できるの？という疑問は生じるかもしれませんが、できます。
実装の仕方は insert-erase ベースと merge-split ベースの二種類があり、お好みの方針で実装すればよいです。
この部分についても細かく話してもよいのですが、今回したい話としては脱線するため、思い切って割愛します。

参考文献と実装例を書いておいたので、余力がある人は見てみてください。

プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～ | PPT
Treap - Algorithms for Competitive Programming

using namespace std;

typedef struct Node {
    int val;
    int priority;
    int cnt;
    int sum;
    Node* left;
    Node* right;

    Node(int val, int priority)
        : val(val),
          priority(priority),
          cnt(0),
          sum(0),
          left(nullptr),
          right(nullptr) {}
} Node;

class Treap {
   private:
    Node* root;

    random_device seed_gen;
    mt19937 engine{seed_gen()};
    uniform_int_distribution<int> distribution{INT_MIN, INT_MAX};

    int count(Node* t) { return !t ? 0 : t->cnt; }
    int sum(Node* t) { return !t ? 0 : t->sum; }
    Node* update(Node* t) {
        if (t) {
            t->cnt = count(t->left) + count(t->right) + 1;
            t->sum = sum(t->left) + sum(t->right) + t->val;
        }
        return t;
    }

    // merge Node* l and Node *r into unique tree
    // this function is under assumption that
    // any node value of l <= any node value of r
    Node* merge(Node* l, Node* r) {
        if (!l || !r) return l ? l : r;
        if (l->priority > r->priority) {
            l->right = merge(l->right, r);
            return update(l);
        } else {
            r->left = merge(l, r->left);
            return update(r);
        }
    }

    // split Node* into two trees (l,r), l has val <=v, r tree has val >k
    void split(Node* t, int v, Node*& l, Node*& r) {
        if (!t) {
            l = r = nullptr;
            return;
        } else if (t->val <= v) {
            split(t->right, v, t->right, r);
            l = update(t);
            return;
        } else {
            split(t->left, v, l, t->left);
            r = update(t);
            return;
        }
    }

    // insert item into t
    void insert(Node*& t, Node* item) {
        if (!t) {
            t = item;
            return;
        }
        Node *t1, *t2;
        split(t, item->val, t1, t2);
        t = merge(merge(t1, item), t2);
    }

    // erase value v from t
    void erase(Node*& t, int v) {
        if (!t) return;
        if (t->val == v) {
            Node* old_t = t;
            t = merge(t->left, t->right);
            delete old_t;
            return;
        } else if (t->val > v) {
            erase(t->left, v);
            return;
        } else {
            erase(t->right, v);
            return;
        }
    }

    void print(Node* t, int depth) {
        if (!t) {
            for (int i = 0; i < depth; i++) cout << "  ";
            cout << "null" << endl;
            return;
        } else {
            print(t->right, depth + 1);
            for (int i = 0; i < depth; i++) cout << "  ";
            cout << "val: " << t->val << ", " << "priority: " << t->priority
                 << endl;
            print(t->left, depth + 1);
        }
    }

   public:
    Treap() { root = nullptr; }
    void insert(int val) { insert(root, new Node(val, distribution(engine))); }
    void erase(int val) { erase(root, val); };

    void print() { print(root, 0); }
};

いったんは、こんな感じで挿入・削除・検索などの操作を $O(log N)$ で実現できるらしい、と思ってください。

あらためて MetaHackerCup の問題を考える…が…

さてここまでで、 Treap がどういったものかを説明しました。
Treap は、乱数を使うことで挿入・削除・検索などの操作を $O(log N)$ で実現できるデータ構造でしたね。
それでは改めて、 Meta Hacker Cup の解説が言っていたことを思い出してみましょう。

原文を意訳した前回の記事から抜粋すると。

つまりは、特定の P に値を入れることと、P以前の値を1引くという操作を高速に（データ量に触れていませんが、この処理を $O(log N)$ で）計算できれば良い。こういうのに便利なデータ構造として Treap ってのがあるので、それをうまく使えば計算できるよ。

とのことでした。

つまり、今回の問題を解くために求められていることは、

特定の P に値を入れること
P 以前のすべての値を１引くこと

を、 $O(log N)$ で計算することです。

…何か話がかみ合っていないような、変な感じがしますよね？

Treap は挿入・削除・検索などの操作を $O(log N)$ で実現できるデータ構造、とお勉強してきたわけですが、
上述の操作を $O(log N)$ で操作できるって話は出てこなかったし、工夫してどうにかなる気も一切しません。

一体なにがどうなっているんだ…となると思いますし、実際僕もここで思い悩みました。

さんざん悩んだ挙句に理解したことの結論を言うと
「Treap は Treap でも、 Meta Hacker Cup でつかうのは Implicit Treap の方」
ということだったようでした。

実は、ここまで学んできた Treap の他に Treap の亜種みたいなのがあるんですね。

参考文献

平衡二分探索木とTreap Implicit Treap - joeの日記

次はそれを見ていきましょう。

Implicit Treap とは何か

Implicit Treap 基礎

Implicit Treap は Treap とは打って変わって、データの大小関係は考えないデータ構造です。
どっちかというと二分探索木というより vector なイメージに近く、以下のような操作が行えます。

(0以上配列長未満の) 位置 p にデータ xを格納する
(0以上配列長未満の) 位置 p のデータを削除する

なんだこれは、ただ配列とか vector とか使えばいいだけじゃないか、と思うかもしれませんが、いったんその気持ちは飲み込んでください。
これと Treap と何の関係があるんだ、という話をまずしていきます。

二分探索木って vector に対応付けられるよね、という話

突然ですが、二分探索木は木のノードを要素の大小をもとに左右に振り分ける特性上、
しかるべき順序でみたら、データが昇順に並んでいるとみることができます。
直観的に図示するなら、以下のような感じです。

この意味で、二分探索木は vector と対応付けられる、ということができます。これは一対一対応ではなくて、二分探索木が定まれば vector は定まるが、 vecotr に対応する二分探索木は何通りか考えられます。例えば、同じ vecotr でも異なる二分探索木として以下のようなものも作れますね。

あらためて、 Implicit Treap とは何なのか？

先ほどの議論を踏まえて Implicit Treap について一言で説明するなら、 Implicit Treap は、

データそのものでなく、データの位置情報 p を使ってデータを二分探索木状に格納する。
二分木の構築の仕方として、 Treap の概念を使う

といったものです。

Step 1 は vector [100] に対応する木を構築したい。ノード追加順は乱数に従い [100] とする。
Step 2 は vector [100, 200] に対応する木を構築したい。ノード追加順は乱数に従い [200, 100] とする
Step 3 は vector [100, 300, 200] に対応する木を構築したい。ノード構築順は乱数に従い [300, 200, 100] とする。
Step 4 は vector [100, 400, 300, 200] に対応する木を構築したい。ノード構築順は乱数に従い [300, 200, 100, 400] とする。
Step 5 は vector [100, 400, 500, 300, 200] に対応する木を構築したい。ノード構築順は乱数に従い [300, 200, 100, 500, 400] とする。
Step 6 は vector [100, 400, 600, 500, 300, 200] に対応する木を構築したい。ノード追加順は乱数に従い [300, 200, 100, 500, 400, 600] とする。

といった具合。青丸で追加したのが各要素の index で、
この index の配置が通常の Treap のようになっている、というのが今回のミソとなります。

実装例

using namespace std;

typedef struct Node {
    int val;
    int priority;
    int cnt;
    Node* left;
    Node* right;

    Node(int val, int priority)
        : val(val), priority(priority), cnt(1), left(nullptr), right(nullptr) {}
} Node;

class ImplicitTreap {
   private:
    Node* root;

    random_device seed_gen;
    mt19937 engine{seed_gen()};
    uniform_int_distribution<int> distribution{INT_MIN, INT_MAX};

    int count(Node* t) { return !t ? 0 : t->cnt; }

    Node* update(Node* t) {
        if (t) {
            t->cnt = count(t->left) + count(t->right) + 1;
        }
        return t;
    }

    // merge Node* l and Node *r into unique tree
    Node* merge(Node* l, Node* r) {
        if (!l || !r) return l ? l : r;
        if (l->priority > r->priority) {
            l->right = merge(l->right, r);
            return update(l);
        } else {
            r->left = merge(l, r->left);
            return update(r);
        }
    }

    // split Node* into l=[0,k), r=[k,n)
    pair<Node*, Node*> split(Node* t, int k) {
        if (!t) return make_pair(nullptr, nullptr);
        if (count(t->left) >= k) {
            pair<Node*, Node*> s = split(t->left, k);
            t->left = s.second;
            return make_pair(s.first, update(t));
        } else {
            pair<Node*, Node*> s = split(t->right, k - count(t->left) - 1);
            t->right = s.first;
            return make_pair(update(t), s.second);
        }
    }

    // insert item into pos of t
    void insert(Node*& t, int pos, Node* item) {
        if (!t) {
            t = item;
            return;
        }
        pair<Node*, Node*> s = split(t, pos);
        t = merge(merge(s.first, item), s.second);
    }

    // erase t[pos]
    void erase(Node*& t, int pos) {
        if (!t) return;
        pair<Node*, Node*> p = split(t, pos + 1);
        pair<Node*, Node*> p2 = split(p.first, pos);
        if (p2.second) delete p2.second;
        t = merge(p2.first, p.second);
    }

    void print(Node* t, int depth) {
        if (!t) {
            for (int i = 0; i < depth; i++) cout << "  ";
            cout << "null" << endl;
            return;
        } else {
            print(t->right, depth + 1);
            for (int i = 0; i < depth; i++) cout << "  ";
            cout << "val: " << t->val << ", " << "priority: " << t->priority
                 << ", " << "count: " << t->cnt << endl;
            print(t->left, depth + 1);
        }
    }

   public:
    ImplicitTreap() { root = nullptr; }
    void insert(int pos, int val) {
        insert(root, pos, new Node(val, distribution(engine)));
    }
    void erase(int val) { erase(root, val); };

    void print() { print(root, 0); }
};

Implicit Treap は何がうれしいか。

さて、ぐにゃぐにゃと説明を続けてきましたが、ここまでを改めてまとめると、

Implicit Treap は以下の操作を $O(logN)$ でできる、というものでした

位置 p にデータ x を追加する
位置 p にあるデータを削除する。

これだけだと、何がうれしいねん、ですよね。
複雑なことをしただけで実現できる操作も大したことがないですし。

Implicit Treap のうれしいところというのは、この形でデータを格納することによって、
任意の部分木が特定の vector の範囲に対応付けられることにあります。

これによって範囲を取り扱う計算とかがかなりしやすくなっており、
補助データを追加するなどの実装追加を行うことによって、以下のような操作も高速で計算することが可能になっています。

特定範囲の中での最小値の検出
特定範囲の中での最大値の検出
特定範囲の値の和の検出
特定範囲に対する加算
特定範囲の reverse （ただし、下記実装例には含まれません)

min, max, sum, add を実装した Treap の実装例

using namespace std;
typedef struct Node {
    int val;
    int priority;
    int cnt;
    int min;
    int max;
    int acc;
    ll sum;
    Node* left;
    Node* right;

    Node(int val, int priority)
        : val(val),
          priority(priority),
          cnt(1),
          sum(val),
          min(val),
          max(val),
          acc(0),
          left(nullptr),
          right(nullptr) {}
} Node;

class ImplicitTreap {
   private:
    Node* root;

    random_device seed_gen;
    mt19937 engine{seed_gen()};
    uniform_int_distribution<int> distribution{INT_MIN, INT_MAX};

    int count(Node* t) { return !t ? 0 : t->cnt; }
    ll sum(Node* t) { return !t ? 0 : t->sum; }
    int getMax(Node* t) { return !t ? INT_MIN : t->max; }
    int getMin(Node* t) { return !t ? INT_MAX : t->min; }

    // update information of t using information of its children
    // this function assumes all the information of the child are updated
    Node* update(Node* t) {
        if (t) {
            t->cnt = count(t->left) + count(t->right) + 1;
            t->sum = sum(t->left) + sum(t->right) + t->val;
            t->min = min(t->val, min(getMin(t->left), getMin(t->right)));
            t->max = max(t->val, max(getMax(t->left), getMax(t->right)));
        }
        return t;
    }

    // push acc, lazy info of node t into its child
    void push(Node* t) {
        if (t) {
            if (t->left) {
                t->left->acc += t->acc;
                t->left->max = t->left->max + t->acc;
                t->left->min = t->left->min + t->acc;
                t->left->sum = t->left->sum + (t->left->cnt) * t->acc;
            }
            if (t->right) {
                t->right->acc += t->acc;
                t->right->max = t->right->max + t->acc;
                t->right->min = t->right->min + t->acc;
                t->right->sum = t->right->sum + (t->right->cnt) * t->acc;
            }
            t->val = t->val + t->acc;
            t->acc = 0;
        }
    }

    // merge Node* l and Node *r into unique tree
    Node* merge(Node* l, Node* r) {
        if (l) push(l);
        if (r) push(r);
        if (!l || !r) return l ? l : r;
        if (l->priority > r->priority) {
            l->right = merge(l->right, r);
            return update(l);
        } else {
            r->left = merge(l, r->left);
            return update(r);
        }
    }

    // split Node* into l=[0,k), r=[k,n)
    pair<Node*, Node*> split(Node* t, int k) {
        if (!t) return make_pair(nullptr, nullptr);
        push(t);
        if (count(t->left) >= k) {
            pair<Node*, Node*> s = split(t->left, k);
            t->left = s.second;
            return make_pair(s.first, update(t));
        } else {
            pair<Node*, Node*> s = split(t->right, k - count(t->left) - 1);
            t->right = s.first;
            return make_pair(update(t), s.second);
        }
    }

    // insert item into pos of t
    void insert(Node*& t, int pos, Node* item) {
        if (!t) {
            t = item;
            return;
        }
        pair<Node*, Node*> s = split(t, pos);
        t = merge(merge(s.first, item), s.second);
    }

    // erase t[pos]
    void erase(Node*& t, int pos) {
        if (!t) return;
        pair<Node*, Node*> p = split(t, pos + 1);
        pair<Node*, Node*> p2 = split(p.first, pos);
        if (p2.second) delete p2.second;
        t = merge(p2.first, p.second);
    }

    void print(Node* t, int depth) {
        if (!t) {
            for (int i = 0; i < depth; i++) cout << "  ";
            cout << "null" << endl;
            return;
        } else {
            print(t->right, depth + 1);
            for (int i = 0; i < depth; i++) cout << "  ";
            cout << "val: " << t->val << ", " << "priority: " << t->priority
                 << ", " << "count: " << t->cnt << ", " << "sum: " << t->sum
                 << ", " << "max: " << t->max << ", " << "min: " << t->min
                 << ", " << "acc: " << t->acc << endl;
            print(t->left, depth + 1);
        }
    }

    // return the sum of [left,right)
    ll sum(Node*& t, int left, int right) {
        pair<Node*, Node*> p = split(t, right);
        pair<Node*, Node*> p2 = split(p.first, left);
        ll ans = sum(p2.second);
        t = merge(merge(p2.first, p2.second), p.second);
        return ans;
    }

    // return the min of [left,right)
    ll getMin(Node*& t, int left, int right) {
        pair<Node*, Node*> p = split(t, right);
        pair<Node*, Node*> p2 = split(p.first, left);
        ll ans = getMin(p2.second);
        t = merge(merge(p2.first, p2.second), p.second);
        return ans;
    }

    // return the max of [left,right)
    ll getMax(Node*& t, int left, int right) {
        pair<Node*, Node*> p = split(t, right);
        pair<Node*, Node*> p2 = split(p.first, left);
        ll ans = getMax(p2.second);
        t = merge(merge(p2.first, p2.second), p.second);
        return ans;
    }

    // add value to the all elements in [left,right]
    void add(Node*& t, int left, int right, int value) {
        pair<Node*, Node*> p = split(t, right);
        pair<Node*, Node*> p2 = split(p.first, left);
        p2.second->acc += value;
        t = merge(merge(p2.first, p2.second), p.second);
    }

   public:
    ImplicitTreap() { root = nullptr; }

    // insert val into ImplicitTreap[pos]
    void insert(int pos, int val) {
        insert(root, pos, new Node(val, distribution(engine)));
    }
    // erase ImplicitTreap[pos]
    void erase(int pos) { erase(root, pos); };

    // sum ImplicitTreap[left,right)
    ll sum(int left, int right) { return sum(root, left, right); }

    // max ImplicitTreap[left,right)
    int getMax(int left, int right) { return getMax(root, left, right); }

    // min ImplicitTreap[left,right)
    int getMin(int left, int right) { return getMin(root, left, right); }

    // add value to all of ImplicitTreap[left,right)
    void add(int left, int right, int value) { add(root, left, right, value); }

    // print
    void print() { print(root, 0); }
};

ここまでくると少しうまみを感じれてきますね。
競技プログラミングにおいて範囲加算・減算などをする際によく用いられるデータ構造には LazySegmentTree とかもありますが、範囲 reverse などが Implicit Treap に優位性があるっぽいです。

次回予告

さて、ここまでの話を改めてまとめると

Implicit Treap は以下の操作を $O(log N)$ で行えるデータ構造でした。

ある位置 p に要素 x を挿入する
ある位置 p にある要素を削除する
ある範囲の要素の最大値を計算する
ある範囲の要素の最小値を計算する
ある範囲の要素すべての総和を計算する
ある範囲の要素すべてに値 a を加算する
ある範囲の要素を左右反転させる

次回は、このデータ構造を使って改めて MetaHackerCup 2024 PracticeRound D2 問題を解いていきましょう。

やおよろず

ゆるふわな内容を書いても良い。と言うか何でも良い。そんな自由度の高いブログをめざします。

MetaHackerCup 2024 PracticeRound D 問題を語るその３：Treap って色々あんねん