Fenwick Tree Index Chains

Problem

Fenwick tree cells are indexed from 1. Given array length n and a 0-based index i, return [update_chain, prefix_chain]. update_chain lists the cells a point update at i visits: i + 1, then x + (x & -x) while x <= n. prefix_chain lists the cells the prefix-sum query ending at i visits: i + 1, then x - (x & -x) down to 1. Assume 0 <= i < n.

Hint

Walk parent indices with x += x & -x for updates and x -= x & -x for prefix sums.

Test cases

case 1

in: [8,0]

expected: [[1,2,4,8],[1]]

case 2

in: [8,5]

expected: [[6,8],[6,4]]

case 3

in: [1,0]

expected: [[1],[1]]

case 4

in: [10,9]

expected: [[10],[10,8]]

Starter codePython

def fenwick_index_chains(n, i):
    # Your code here
    pass

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