Fennic tree

Tree structure that allows efficient both partial sum computation and element updating

Abbreviated as [BIT

Kazuhiro Hosaka (Department of Mathematics, The University of Tokyo)

13th JOI Spring Training Camp

2014/03/19

Can be used as a data structure for fast retrieval of the kth value

Adding and deleting to a set and getting kth

A simple way to do this is to prepare an array of size D of the value range and set 1 where there is a value

Can be added and deleted with O(1)

Acquisition of KTH is slow because it counts from the end.

Make this a BIT.

BIT is a partial sum of O(logD)

We can do a bifurcated search for this.

O(logD) see Hosaka's data if you devise it.

However, additions and deletions are O(logD)

When you want to know the next value of a value in a set

First take the sum up to that value, add 1, and search for the bisection

If we repeat this, we can also "get something larger than a certain value.

code:python

N = 1000

def bit_add(pos, val):

x = pos

while x <= N:

x += x & -x # (x & -x) = rightmost 1 = block width

def bit_sum(pos):

ret = 0

x = pos

while x > 0:

x -= x & -x

return ret

def bit_bisect(lower):

"find a s.t. v1 + v2 + ... + va >= lower"

x = 0

k = 1 << (N.bit_length() - 1) # largest 2^m <= N

while k > 0:

x += k

k //= 2

return x + 1

bit_add(12, 1)

bit_add(34, 1)

bit_add(56, 1)

print(bit_sum(20)) # => 1

print(bit_sum(40)) # => 2

print(bit_sum(60)) # => 3

print(bit_bisect(2)) # => 34

---