data_structures.binary_tree.maximum_fenwick_tree

Classes

MaxFenwickTree

Maximum Fenwick Tree

Module Contents

class data_structures.binary_tree.maximum_fenwick_tree.MaxFenwickTree(size: int)

Maximum Fenwick Tree

More info: https://cp-algorithms.com/data_structures/fenwick.html

>>> ft = MaxFenwickTree(5)
>>> ft.query(0, 5)
0
>>> ft.update(4, 100)
>>> ft.query(0, 5)
100
>>> ft.update(4, 0)
>>> ft.update(2, 20)
>>> ft.query(0, 5)
20
>>> ft.update(4, 10)
>>> ft.query(2, 5)
20
>>> ft.query(1, 5)
20
>>> ft.update(2, 0)
>>> ft.query(0, 5)
10
>>> ft = MaxFenwickTree(10000)
>>> ft.update(255, 30)
>>> ft.query(0, 10000)
30
>>> ft = MaxFenwickTree(6)
>>> ft.update(5, 1)
>>> ft.query(5, 6)
1
>>> ft = MaxFenwickTree(6)
>>> ft.update(0, 1000)
>>> ft.query(0, 1)
1000

static get_next(index: int) → int

Get next index in O(1)

static get_prev(index: int) → int

Get previous index in O(1)

query(left: int, right: int) → int

Answer the query of maximum range [l, r) in O(lg^2 N)

Parameters:

left: left index of query range (inclusive) right: right index of query range (exclusive)

Returns:

Maximum value of range [left, right)

update(index: int, value: int) → None

Set index to value in O(lg^2 N)

Parameters:

index: index to update value: value to set

Returns:

None

arr

size

tree