LeetCode 303. Range Sum Query -

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];
    }
};