Algorithms and Data Structures · Middle · Question 56 of 75
How do you answer "sum of elements from i to j" many times on a static array?
- 1Sort the array and use binary search for each query
- ✓Correct answer: Prefix sums once, then
prefix[j + 1] - prefix[i]per query - 3Recompute the sum with a loop for every single query
Explanation
Preprocessing is O(n) and every query is O(1). If the array also changes between queries, prefix sums break and you need a Fenwick or segment tree.