easyArrays & HashingAI-applied~11 min
Token Cost Prefix Sum
Each message in a chat transcript has a token cost. A billing view repeatedly asks for the total tokens between two message indices. Precompute so each range query is constant time.
Problem
Given an integer array costs, design a structure that, after O(n) preprocessing, answers sumRange(i, j) — the inclusive sum of costs[i..j] — in O(1) per query.
Input
An array costs of length n (1 ≤ n ≤ 10^4) and multiple (i, j) queries with 0 ≤ i ≤ j < n.
Output
For each query, the inclusive range sum.
Constraints
- Preprocessing is O(n)
- Each query must be O(1)
- Values may be negative
Examples
Example 1
Input
costs = [3, 1, 4, 1, 5], sumRange(1, 3)
Output
6
1 + 4 + 1 = 6.
Example 2
Input
costs = [3, 1, 4, 1, 5], sumRange(0, 4)
Output
14
Sum of the whole array.