A Segment Tree is a data structure that stores information about array intervals as a tree. This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array. This includes finding the sum of consecutive array elements $$$a[l \dots r]$$$ , or finding the minimum element in a such a range in $$$O(\log n)$$$ time. Between answering such queries, the Segment Tree allows modifying the array by replacing one element, or even changing the elements of a whole subsegment (e.g. assigning all elements $$$a[l... r]$$$ to any value, or adding a value to all element in the subsegment).

Using pip:

from segment_tree import *
array = [3, 1, 5, 3, 13, 7, 2, 7, 2]
tree = SegmentTree(array)

t.query(1, 3, "sum") # 9
t.update(0, 10) # [10, 1, 5, 3, 13, 7, 2, 7, 2]
t.query(0, 8, "min") # 0
t.update(2, -1) # [10, 1, -1, 3, 13, 7, 2, 0, 2]
t.query(0, 2, "min") # -1

from segment_tree import *
array = [1, 2, 3, 4, 5]
t = SegmentTree(array)
t.update_range(0, 2, 6) # 6 6 6 4 5
t.update_range(1, 4, 2) # 6 2 2 2 2
t.query(0, 3, "min") # 2

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Using pip again:

fenwick_tree = FenwickTree(n)
for x in range(n):
    fenwick_tree.add(x, x + 1)

from __future__ import print_function

from fenwick import FenwickTree

n = 10

print('Note: Indexing is 0-based.')
print()

print('*******************************************')
print('* Initialize FenwickTree and update        ')
print('* frequencies one at a time.               ')
print('*******************************************')
print()

fenwick_tree = FenwickTree(n)
for x in range(n):
    fenwick_tree.add(x, x + 1)

print('*******************************************')
print('* Initialize FenwickTree using existing    ')
print('* frequencies.                             ')
print('*******************************************')
print()

fenwick_tree = FenwickTree(n)
f = range(1, n + 1)
fenwick_tree.init(f)

print('*******************************************')
print('* Calculate and print sum of all           ')
print('* frequencies                              ')
print('*******************************************')
print()

sum_all = fenwick_tree.prefix_sum(n)
print(sum_all)
print()

print('*******************************************')
print('* Calculate and print sum of frequencies   ')
print('* 2 through 8.                           ')
print('*******************************************')
print()

sum_2_8 = fenwick_tree.range_sum(2, 9)
print(sum_2_8)
print()

print('*******************************************')
print('* Calculate and print frequencies 5       ')
print('* through 9.                              ')
print('*******************************************')
print()

for x in range(5, 10):
    print(fenwick_tree[x])
print()

print('*******************************************')
print('* Retrieve and print all frequencies.      ')
print('*******************************************')
print()

print(fenwick_tree.frequencies())

This data structure provides the following capabilities. We are given several elements, each of which is a separate set. A DSU will have an operation to combine any two sets, and it will be able to tell in which set a specific element is. The classical version also introduces a third operation, it can create a set from a new element.

Yes, you are right! We are using pip again:

>>> from disjoint_set import DisjointSet
>>> ds = DisjointSet()
>>> ds.find(1)
1
>>> ds.union(1,2)
>>> ds.find(1)
2
>>> ds.find(2)
2
>>> ds.connected(1,2)
True
>>> ds.connected(1,3)
False

>>> "a" in ds
False
>>> ds.find("a")
'a'
>>> "a" in ds
True

>>> list(ds)
[(1, 2), (2, 2), (3, 3), ('a', 'a')]

>>> list(ds.itersets())
[{1, 2}, {3}, {'a'}]

A treap is a data structure which combines binary tree and binary heap (hence the name: tree + heap $$$\Rightarrow$$$ Treap).

More specifically, treap is a data structure that stores pairs $$$(X, Y)$$$ in a binary tree in such a way that it is a binary search tree by $$$X$$$ and a binary heap by $$$Y$$$. If some node of the tree contains values $$$(X_0, Y_0)$$$ , all nodes in the left subtree have $$$X \leq X_0$$$ , all nodes in the right subtree have $$$X_0 \leq X$$$, and all nodes in both left and right subtrees have $$$Y \leq Y_0$$$.

A treap is also often referred to as a "cartesian tree", as it is easy to embed it in a Cartesian plane.

Again, as I mentioned, Python is the most powerful language for CP, we will use pip again:

>>> import treap
>>> t = treap.treap()
>>> import random
>>> for i in range(20):
...    t[random.random()] = i
...
>>> list(t)
[0.011795687154763312, 0.0695864396266509, 0.15741892655439682, 0.18718082546304682, 0.1910965922423038, 0.22849105220538402, 0.276078590851345, 0.3166512089228003, 0.3456516881327997, 0.3543869818366584, 0.4022879538597536, 0.4519316126668157, 0.46329639459896466, 0.4873225275394878, 0.5866856381825849, 0.6403758625610735, 0.6936888466959068, 0.7843975080768091, 0.8888622013819216, 0.9047894146828958]
>>> t.find_min()
0.011795687154763312
>>> t.find_max()
0.9047894146828958