Fenwick Tree Range XOR

Problem

Support point updates and range XOR queries with a Fenwick tree.

nums is the initial array. queries is a list of ["update", i, val] (set nums[i] = val) or ["query", l, r] (XOR of nums[l..r] inclusive). XOR is its own inverse, so the binary indexed tree simply replaces addition with the xor operator.

Return the list of query results.

Hint

A range XOR is prefix(r) xor prefix(l - 1), just like a range sum with subtraction replaced.

Test cases

case 1

in: [[1,2,3],[["query",0,2],["update",1,0],["query",0,2]]]

expected: [0,2]

case 2

in: [[5],[["query",0,0]]]

expected: [5]

case 3

in: [[0,0,0],[["update",1,7],["query",0,2],["query",1,1]]]

expected: [7,7]

case 4

in: [[1,1],[["query",0,1]]]

expected: [0]

Starter codePython

def xor_range_queries(nums, queries):
    # Your code here
    pass

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