C++/Java/Python O(n) build O(1) query


  • 0

    The problem is easy. The array is not changing therefore we don't need a Binary Indexed Tree or Segment Tree. Prefix sums can do the trick perfectly.

    One argument is that reusing the nums array for underlying data structure is not a good idea. We should allocate new memory to store the sums in the constructor.

    Java

    private int[] sums;
    
    public NumArray(int[] nums) {
        sums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; ++i)
            sums[i + 1] = sums[i] + nums[i];
    }
    
    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
    

    Java with ArrayList

    private List<Integer> sums = new ArrayList<>(Collections.singletonList(0));
    
    public NumArray(int[] nums) {
        for (int x : nums)
            sums.add(sums.get(sums.size() - 1) + x);
    }
    
    public int sumRange(int i, int j) {
        return sums.get(j + 1) - sums.get(i);
    }
    

    C++

    vector<int> sums = {0};
    NumArray(vector<int> &nums) {
        for (auto x: nums)
            sums.push_back(sums.back() + x);
    }
    int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
    

    Python

    def __init__(self, nums):
        self.sums = [0]
        for x in nums:
            self.sums.append(self.sums[-1] + x)
    
    def sumRange(self, i, j):
        return self.sums[j + 1] - self.sums[i]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.