pyrival.data_structures¶

pyrival.data_structures.BitArray¶

class pyrival.data_structures.BitArray.BitArray(size)¶

Bases: object

implements bitarray using bytearray

pyrival.data_structures.CFraction¶

pyrival.data_structures.CFraction.CFrac2Frac(cfrac)¶

pyrival.data_structures.CFraction.CFraction(frac)¶

pyrival.data_structures.DisjointSetUnion¶

class pyrival.data_structures.DisjointSetUnion.DisjointSetUnion(n)¶

Bases: object

find(a)¶

set_size(a)¶

union(a, b)¶

class pyrival.data_structures.DisjointSetUnion.UnionFind(n)¶

Bases: object

find(a)¶

union(a, b)¶

pyrival.data_structures.FenwickTree¶

class pyrival.data_structures.FenwickTree.FenwickTree(x)¶

Bases: object

findkth(k)¶: Find largest idx such that sum(bit[:idx]) <= k

query(end)¶: calc sum(bit[:end])

update(idx, x)¶: updates bit[idx] += x

pyrival.data_structures.Fraction¶

class pyrival.data_structures.Fraction.Fraction(num=0, den=1)¶: Bases: object

pyrival.data_structures.Fraction.gcd(x, y)¶: greatest common divisor of x and y

pyrival.data_structures.Fraction.limit_denominator(frac, max_den=1000000)¶

pyrival.data_structures.Heap¶

class pyrival.data_structures.Heap.Heap(iterable=None, reverse=False)¶

Bases: object

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

replace(item)¶

class pyrival.data_structures.Heap.OrderHeap(iterable=None, key=<function OrderHeap.<lambda>>, reverse=False)¶

Bases: pyrival.data_structures.Heap.Heap

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

replace(item)¶

class pyrival.data_structures.Heap.RemovalHeap(iterable=None, reverse=False)¶

Bases: pyrival.data_structures.Heap.Heap

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

remove(item)¶

replace(item)¶

sweep()¶

class pyrival.data_structures.Heap.XHeap(iterable=None, key=<function XHeap.<lambda>>, reverse=False)¶

Bases: pyrival.data_structures.Heap.Heap

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

remove(item)¶

replace(item)¶

sweep()¶

pyrival.data_structures.LazySegmentTree¶

class pyrival.data_structures.LazySegmentTree.LazySegmentTree(data, default=0, func=<built-in function max>)¶

Bases: object

add(start, stop, value)¶: lazily add value to [start, stop)

query(start, stop, default=0)¶: func of data[start, stop)

pyrival.data_structures.LinkedList¶

class pyrival.data_structures.LinkedList.LinkedList(iterable=None)¶

Bases: object

after(node)¶

append(value)¶

appendleft(value)¶

before(node)¶

get_node(index)¶

insert(index, value)¶

insert_after(node, value)¶

insert_between(node, left_node, right_node)¶

merge_left(other)¶

merge_right(other)¶

pop(node=None)¶

to_list()¶

class pyrival.data_structures.LinkedList.Node(value)¶: Bases: object

pyrival.data_structures.Node¶

class pyrival.data_structures.Node.Node(value)¶: Bases: object

pyrival.data_structures.PersistentSegTree¶

pyrival.data_structures.PersistentSegTree.create(n)¶: create a persistant segment tree of size n

pyrival.data_structures.PersistentSegTree.minimum(ind, l, r, n)¶: find mimimum of set[l:r] for segment tree ind, of size n

pyrival.data_structures.PersistentSegTree.setter(ind, i, val, n)¶: set set[i] = val for segment tree ind, of size n

pyrival.data_structures.RangeQuery¶

class pyrival.data_structures.RangeQuery.RangeQuery(data, func=<built-in function min>)¶

Bases: object

query(start, stop)¶: func of data[start, stop)

pyrival.data_structures.SegmentTree¶

class pyrival.data_structures.SegmentTree.SegmentTree(data, default=0, func=<built-in function max>)¶

Bases: object

query(start, stop)¶: func of data[start, stop)

pyrival.data_structures.SortedList¶

The “sorted list” data-structure, with amortized O(n^(1/3)) cost per insert and pop.

Example:

A = SortedList() A.insert(30) A.insert(50) A.insert(20) A.insert(30) A.insert(30)

print(A) # prints [20, 30, 30, 30, 50]

print(A.lower_bound(30), A.upper_bound(30)) # prints 1 4

print(A[-1]) # prints 50 print(A.pop(1)) # prints 30

print(A) # prints [20, 30, 30, 50] print(A.count(30)) # prints 2

class pyrival.data_structures.SortedList.FenwickTree(x)¶

Bases: object

find_kth(k)¶: Find largest idx such that sum(bit[:idx]) <= k

update(idx, x)¶: updates bit[idx] += x

class pyrival.data_structures.SortedList.SortedList(iterable=())¶

Bases: object

block_size = 700¶

count(x)¶

insert(x)¶

lower_bound(x)¶

pop(k=-1)¶

upper_bound(x)¶

pyrival.data_structures.Treap¶

class pyrival.data_structures.Treap.TreapHashMap(data=None)¶

Bases: pyrival.data_structures.Treap.TreapMultiSet

add(key)¶

discard(key)¶

get(key, default=None)¶

remove(key)¶

class pyrival.data_structures.Treap.TreapHashSet(data=None)¶

Bases: pyrival.data_structures.Treap.TreapMultiSet

add(key)¶

discard(key)¶

remove(key)¶

class pyrival.data_structures.Treap.TreapMultiSet(data=None)¶

Bases: object

add(key)¶

ceiling(key)¶

discard(key)¶

floor(key)¶

higher(key)¶

lower(key)¶

max()¶

min()¶

remove(key)¶

root = 0¶

size = 0¶

class pyrival.data_structures.Treap.TreapSet(data=None)¶

Bases: pyrival.data_structures.Treap.TreapMultiSet

add(key)¶

pyrival.data_structures.Treap.treap_builder(sorted_data)¶: Build a treap in O(n) time using sorted data

pyrival.data_structures.Treap.treap_ceiling(root, key)¶

pyrival.data_structures.Treap.treap_create_node(key)¶

pyrival.data_structures.Treap.treap_erase(root, key)¶

pyrival.data_structures.Treap.treap_floor(root, key)¶

pyrival.data_structures.Treap.treap_higher(root, key)¶

pyrival.data_structures.Treap.treap_insert(root, key)¶

pyrival.data_structures.Treap.treap_insert_unique(root, key)¶

pyrival.data_structures.Treap.treap_lower(root, key)¶

pyrival.data_structures.Treap.treap_max(root)¶

pyrival.data_structures.Treap.treap_merge(left, right)¶

pyrival.data_structures.Treap.treap_min(root)¶

pyrival.data_structures.Treap.treap_split(root, key)¶

pyrival.data_structures.Trie¶

class pyrival.data_structures.Trie.Trie(*words)¶

Bases: object

add(word)¶

pyrival.data_structures.TwoSat¶

class pyrival.data_structures.TwoSat.TwoSat(n)¶

Bases: object

either(x, y)¶: either x or y must be True

set(x)¶: x must be True

solve()¶

pyrival.data_structures.TwoSat.find_SCC(graph)¶

pyrival.data_structures.convex_hull_trick¶

pyrival.data_structures.convex_hull_trick.convex_hull_trick(K, M, integer=True)¶

Given lines on the form y = K[i] * x + M[i] this function returns intervals, such that on each interval the convex hull is made up of a single line. Input:

K: list of the slopes M: list of the constants (value at x = 0) interger: boolean for turning on / off integer mode. Integer mode is exact, it

works by effectively flooring the seperators of the intervals.

Return:: hull_i: on interval j, line i = hull_i[j] is >= all other lines hull_x: interval j and j + 1 is separated by x = hull_x[j], (hull_x[j] is the last x in interval j)

pyrival.data_structures.convex_hull_trick.max_query(x, K, M, hull_i, hull_x)¶: Find maximum value at x in O(log n) time

pyrival.data_structures.tree_repr¶

pyrival.data_structures.tree_repr.tree_repr(tree)¶