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 […]