Persistent Segment Tree Node Count

Problem

Count the nodes a persistent segment tree creates. Build a tree over initial, then apply each update [index, value] to the latest version, copying only the root-to-leaf path. Return [build_nodes, per_update]: build_nodes is the node count of the initial tree and per_update lists how many new nodes each update allocates. Return [0, []] for an empty initial array.

Hint

An update allocates one node per level of the root-to-leaf path; a full tree with n leaves has 2n - 1 nodes.

Test cases

case 1

in: [[0,0,0,0],[[1,5],[3,9],[0,2]]]

expected: [7,[3,3,3]]

case 2

in: [[0],[[0,7]]]

expected: [1,[1]]

case 3

in: [[1,2,3],[[0,9],[2,9],[1,9]]]

expected: [5,[3,2,3]]

Starter codePython

def persistent_node_count(initial, updates):
    # Your code here
    pass

3 test cases · run your code against them in the editor