Add Treap

[LJH-coding]

Treap

Introduction to Treap

//Definition of Binary Search Tree, Heap, and Treap

Split-Merge Tree

Introduction

//How it keep self to balance

Treap node

//Create a Treap node

Merge

//Merge two Treap nodes

Split by key

//according to node's key split it to two nodes

Erase, Insert, K-th element, ... some BST operation

Range Queries

//Split by size, save information in Treap node, pull (merge two nodes and update information)

Lazy Tag

//how to push Treap node's lazy tag to node's son

Range Reverse

//use lazy tag to reverse

O(N) build a Treap

//introduction to cartesian tree

Proof Treap's deep is logN

Problems

//some problems use treap will be better or only can use treap to solve it
//for example: TIOJ 1169, cf 702F

References

https://codeforces.com/blog/entry/84017
https://oi-wiki.org/ds/treap/
https://oi-wiki.org/ds/cartesian-tree/
https://cp-algorithms.com/data_structures/treap.html
https://usaco.guide/adv/treaps?lang=cpp

//sorry for my poor English :(