题目描述

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

The update(i, val) function modifies nums by updating the element at index i to val.

 

题目大意

实现两个操作：更新数组，求数组范围内数字之和。

 

示例

E1

 

解题思路

保存一个vector数组，更新时以O（1）时间复杂度更新，求和时以O（N）时间复杂度遍历数组求和。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

 

代码

class NumArray {public:    NumArray(vector
     
      & nums) {        for(int n : nums)            num.push_back(n);    }        void update(int i, int val) {        num[i] = val;    }        int sumRange(int i, int j) {        int sum = 0;        for(int k = i; k <= j; ++k)            sum += num[k];        return sum;    }    private:    vector
      
        num;};/** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * obj->update(i,val); * int param_2 = obj->sumRange(i,j); */