Range Sum Query - Immutable
给定一个数组，指定两个indices之间(inclusive)的和
如果只是一个函数就非常简单，直接过一遍就可以。但这道题给的是用一个数组构造一次实例，对同一个实例多次调用sumRange函数。这样的话如果每次sumRange都o(n)就非常慢。
solution是在构造函数里面求出来n1, n1 + n2, n1 + n2 + n3.....，然后sumRange里面直接求差，这样构造函数O(n), sumRange O(1)
二维数组版Range Sum
Leetcode 304. Range Sum Query 2D - Immutable, Terence_F的文章
class NumArray {
vector<int> dp {0};
public:
NumArray(vector<int> &nums) {
int sum = 0;
for (int n: nums) {
sum += n;
dp.push_back(sum);
}
}
int sumRange(int i, int j) {
return dp[j + 1] - dp[i];
}
};
