Store sums before each index

Define prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i]. Then the sum of the half-open range [left, right) is prefix[right] - prefix[left].

Building the prefix array takes O(n) time and space. Each later range query takes O(1) time, which pays off when the same array receives many queries.