Treap-koodi

struct Node {
	Node* left;
	Node* right;
	int prior, size;
	int value;
	Node(int v) {
		left = nullptr;
		right = nullptr;
		size = 1;
		prior = rand();
		value = v;
	}
};

// Returns the size of the subtree t
int cnt(Node* t) {
	if (t == nullptr) return 0;
	return t->size;
}

// Updates the size of the subtree t
void upd(Node* t) {
	if (t == nullptr) return;
	t->size = cnt(t->left) + 1 + cnt(t->right);
}

// Put lazy updates here
void push(Node* t) {
	if (t == nullptr) return;
	// Do lazy update
}

// Merges trees left and right into tree t
void merge(Node*& t, Node* left, Node* right) {
	push(left);
	push(right);
	if (left == nullptr) t = right;
	else if(right == nullptr) t = left;
	else {
		if (left->prior > right->prior) {
			merge(left->right, left->right, right);
			t = left;
		}
		else {
			merge(right->left, left, right->left);
			t = right;
		}
	}
	upd(t);
}

// Splits tree t into trees left and right
// Size of tree left will be k
void split(Node* t, Node*& left, Node*& right, int k) {
	if (t == nullptr) {
		left = nullptr;
		right = nullptr;
		return;
	}
	else {
		push(t);
		if (cnt(t->left) >= k) {
			split(t->left, left, t->left, k);
			right = t;
		}
		else {
			split(t->right, t->right, right, k - cnt(t->left) - 1);
			left = t;
		}
	}
	upd(t);
}

int main() {
	Node* tree = nullptr;
	Node* n1 = new Node(3);
	Node* n2 = new Node(2);
	Node* n3 = new Node(4);
	merge(tree, tree, n1);
	merge(n2, n2, n3);
	merge(tree, tree, n2);
	// Now tree is root of a treap which represents array [3, 2, 4]
	Node* t1;
	Node* t2;
	split(tree, t1, t2, 1);
	// Now t1 represents array [3] and t2 represents array [2, 4]
}