Treap

Overview

• What is Treap?
• Why use Treap?
• How to implement Treap?
• PBDS and Rope
• Advanced Topics
• Samples

Note:

• Cover Advanced Topics if time available

Definition

• tree + heap
• tree for data
• heap for shape
• balanced on average if priority is assigned randomly

Binary Search Tree

degenerate BST

Heap

• \(\mathrm{parent > children \quad \forall nodes}\)

Treap

Balance Property

Note:

• a single proof for balance property
• insertion is decided by piority, larger priority -> inserted earlier
• emphasize priority decide insertion order if view tree as final tree
• randomized BST
• size as probability weight implementation
  • when merge, \(\Pr(a ~\text{as root}) = \frac{\text{size}(a)}{\text{size}(a)+\text{size}(b)}\)
  • more rand() calls but use less memory

Usage

• Easy to code balanced BST
• Merge / Split operation
• Implicit Treap
• Serve as powerful interval tree(線段樹)
• Free to add additional features!
• Implementation details will be cover later

Note:

• interval tree? segment tree? 名稱緣由
• Should give a sense that treap is strong
• talk about merge/split a little
• details should be cover in implementation

Implicit Treap

• idea : index as key
• blanced array
• text-editor (rope)

Note:

• when implement, record size instead of index
• interval information maintain

Treap as interval tree

Note:

• talk about concept of merge and split
• cover details and code later

Interval Treap

Note:

• Each point is array value itself and record the interval information of its subtree

Implementation

Note:(can mention a little)

• We use merge-split treap most of the time
• advantages:
  • easy to code (~iterval tree)
  • more powerful (merge and split supported)
• downsides:
  • constant bigger than rotate treap

Treap Node Code

struct Node
{
  int pri, key, sz, val;
  Node *lc, *rc;
  Node(){};
  //syntax sugar
  Node(int val, int key) :pri(rand()), key(key), sz(1), val(val), mark(0) {};
  Node(int val) :pri(rand()), sz(1), val(val), mark(0) {};
}

Note:

• if no srand, rand() result is predictible by problem setter
• and problem setter can 搞你
• Node in merge-split Treap can be seen as subtree rooted at that Node

Basic Operations

Merge

• priority大的當根, 剩下交給子樹處理

• 很清楚的是\(O(\log(n))\)
• 注意到左右永不混雜

Merge

Node* merge(Node* a, Node* b) //key a < key b
{
    if (!a) return b; //base case
    if (!b) return a;
    if(a−>pri > b−>pri)//pri a bigger => a as root
    {
        a−>r = merge(a−>r, b); //key b bigger => merge b and rc of a
        return a;
    }
    //b as root
    b−>l = merge(a, b−>l); //key a smaller => merge a and lc of b
    return b;
}

Note:

• Merge preserve BST order, so when still work on implicit key

Split

• split treap C to treap A and treap B by key value k
• 如果當前的根的key \(\leq\) k
• 根及左子樹都屬於A, 右邊再討論
• 遞迴右邊的結果要接回根當前根的右邊

Split

• split treap C to treap A and treap B by key value k
• \(\text{key}_a \leqslant k < \text{key}_b \quad \forall a \in A,\ b \in B\)
• Q : why heap property still holds

void split(Node* c, int k, Node*& a, Node*& b) 
{
  if (!c) a = b = nullptr; //base case
  else if (c−>key <= k)
  { //key of c is smaller than k =>
    a = c;
    split(c−>r, k, a−>r, b);
  }
  else
  {
    b = c;
    split(c−>l, k, a, b−>l);
  }
}

Note:

• result will store in a, b (passed by reference)
• Answer of Q : because all nodes' children are deeper than themself
• No need to judge priority!!

Split - Implicit Treap

• implicit treap?
• record size and change k while cutting

Note:

• try to code yourself

Insert

• Insert(C, x)
• Split(C, x, A, B)
• Merge(Merge(A, x), B)
• get AxB
• insert interval?

Note:

• interval(as treap) is nothing special

Delete

• Delete(C, x)
• Split(C, <x, A, B), Split(C, x, D, E)
• Merge(A, E)
• get A(no x)E
• delete interval?…delete "single x"?

Note:

• Answer to delete a single x : D = find(C, x), D = Merge(D->lc, D->rc)

For Interval Treap

• very similar to interval tree
• check validity of information!
• write push and pull function for clarity
  • push (down)
    • before use subtrees
    • 根處理好了剩下「推」給子樹處理
  • pull (up)
    • when merge subtrees
    • 子樹處理好的資訊「拉」上來

Note:

• 叫pull up的時候資訊一定要是對的
• 叫push dpwn的時候自己要處理好

Example (POJ 3580 Super Memo)

void add_(Node *&root, int l, int r, int x)
{
  Node *a, *b, *c, *d;
  split(root, r, a, b); //a = [1, r]
  split(a, l-1, c, d); //d = [l, r]
  d->addv += x;
  root = merge(merge(c, d), b);
}

Node *merge(Node *a, Node *b) //key a < key b
{
  if(!a) return b;
  if(!b) return a;
  if(a->pri > b->pri)
  {
    push(a);
    a->rc = merge(a->rc, b);
    pull(a);
    return a;
  }
  push(b);
  b->lc = merge(a, b->lc);
  pull(b);
  return b;
}

void push(Node *a)
{
  if(!a) return;
  if(a->rev)
  {
    swap(a->lc, a->rc);
    if(a->lc) a->lc->rev ^= 1;
    if(a->rc) a->rc->rev ^= 1;
    a->rev = false;
  }
  if(a->addv != 0)
  {
    a->val += a->addv;
    a->minv += a->addv;
    if(a->lc) a->lc->addv += a->addv;
    if(a->rc) a->rc->addv += a->addv;
    a->addv = 0;
  }
  return;
}

void pull(Node *a)
{
  a->sz = sz(a->lc) + sz(a->rc) + 1;
  a->minv = a->val;
  //key : push children before pull (maintain inside) or consider addv lazy mark
  if(a->lc) a->minv = min(a->minv, a->lc->minv + a->lc->addv);
  if(a->rc) a->minv = min(a->minv, a->rc->minv + a->rc->addv);
}

Note:

• From my AC code
• 21277193 maxwill 3580 Accepted 6140K 1532MS G++ 4975B 2020-01-29 13:41:32

PBDS and Rope

• pbds BST : binary search tree
• rope : text editor, implicit BST
• 如果必須實作, ICPC 可以帶模板 但是要夠熟悉賽場上才容易寫得出來變化題

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> ordered_set;

Note:

• pbds is strong, if only need basic treap op (find kth), pbds/rope is enough
• ICPC 是可以帶模板的, 但是要夠熟悉賽場上才容易寫得出來變化題
• quick introduction and jump to details

pbds BST example

• support find_by_order and order_of_key

ordered_set X;
X.insert(1);
X.insert(2);
X.insert(4);
X.insert(8);
X.insert(16);

cout<<*X.find_by_order(1)<<endl; // 2
cout<<*X.find_by_order(2)<<endl; // 4
cout<<*X.find_by_order(4)<<endl; // 16
cout<<(end(X)==X.find_by_order(6))<<endl; // true

cout<<X.order_of_key(-5)<<endl;  // 0
cout<<X.order_of_key(1)<<endl;   // 0
cout<<X.order_of_key(3)<<endl;   // 2
cout<<X.order_of_key(400)<<endl; // 5

rope example

• text-editor-like

typedef rope<char> crope; //crope = rope<char>
rope<int> rp, a, b, c;
rp[x];
rp.at(x);
rp.length();
rp.size();
rp.push_back(x);
rp.insert(pos, x);  //insert x at position pos
rp.erase(pos, x);   //erase x elements from pos
rp.replace(pos, x); //from position pos replace with x
rp.substr(pos, x);  //rp[pos:pos+x]
rp.copy(pos, x, s); //from position pos to pos+x replace with s
a = b + c; //concat

• bulit-in Copy-on-Write

rope<int> *his[100000];
his[i] = new rope<int> (*his[i - 1]);

Advanced Topics

Samples

• POJ 3580 SuperMemo
• UVa 12538 Version Controlled IDE

POJ 3580 SuperMemo

Note:

• SUM x, y => care ADD lazy mark (interval val += interval size*addv)
• sample solution?

UVa 12538 Version Controlled IDE

Conclusion

• Treap is a powerful data structure in competitive programming
• However, many problems that can be solved by Treap have alternatives
• Get familiar with this powerful tool and strengthen your mind

Note:

• https://codeforces.com/contest/847/problem/D
• Treap/BIT/greedy/fastest O(n)

Reference

• Google
• 2016建中校隊培訓講義 by hansonyu123
• PCCA winter camp 廖俊杰(aaaaajack) Treap note
• https://cp-algorithms.com/data_structures/treap.html
• C++ PBDS
• C++ rope
• Markdown slide tutorial
• Original Treap pictures with draw.io
• Latex symbol list

Thanks All