Category: Segment Tree

Written by Bilbo

Range Sum Query 2D

Range Sum Query 2D Immutable Given a matrix. Query the sum of a region specified by the region’s upper left and lower right corner. Binary Index Tree Solution The idea is to insert all items into a BIT sequentially. Then query the BIT m times (assume region is m X n) with range of size […]

Written by Bilbo

Range Sum Query

Range Sum Query Immutable DP Solution First build prefix array of size n + 1. prefix[i] = prefix[i – 1] + nums[i – 1]. Then range sum S[i..j] is prefix[j + 1] – prefix[i]. Time: Build the prefix array O(n); Query range sum: O(1); Space: O(n), prefix array; This file contains bidirectional Unicode text that […]