> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/subarray-sum/range-sum-query-immutable.md).

# Range Sum Query - Immutable

https\://leetcode.com/problems/range-sum-query-immutable/description/

> Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

## Thoughts

这里用到一个常用的小trick, 求数组某段的和相当于总和减去前面的和。

## Code

```
class NumArray {
    int[] f, nums;
    int n;

    public NumArray(int[] nums) {
        this.nums = nums;
        n = nums.length;  
        if (n == 0) {
            return;
        } 
        f = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        if (n == 0) {
            return 0; 
        }
        return f[j] - f[i] + nums[i];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */
```

## Analysis

时间复杂度为一次遍历，O(n)