Sqrt Decomposition Block Sum

Problem

Support point updates and range sums with square-root decomposition.

nums is the initial array. queries is a list of ["update", i, val] or ["query", l, r] (inclusive sum). Elements are grouped into blocks of about sqrt(n), and each block keeps its running sum.

Return the list of query results.

Hint

A range sum touches at most two partial blocks plus a run of whole blocks.

Test cases

case 1

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

expected: [15,16]

case 2

in: [[5],[["query",0,0],["update",0,-2],["query",0,0]]]

expected: [5,-2]

case 3

in: [[],[]]

expected: []

case 4

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

expected: [7]

case 5

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

expected: [10,12,6]

Starter codePython

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

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