data_structures.binary_tree.maximum_fenwick_tree

Attributes

size

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

Updating a smaller sibling preserves the maximum, including after decreases. >>> ft = MaxFenwickTree(8) >>> ft.update(4, 20) >>> ft.update(5, 1) >>> ft.query(0, 6) 20 >>> ft.update(4, 0) >>> ft.query(0, 6) 1 >>> ft.update(5, 0) >>> ft.query(0, 6) 0

Updating a child must also preserve the ancestor’s own array value. >>> ft = MaxFenwickTree(8) >>> ft.update(5, 100) >>> ft.update(4, 0) >>> ft.query(0, 6) 100

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

data_structures.binary_tree.maximum_fenwick_tree.size = 2000