-
Notifications
You must be signed in to change notification settings - Fork 110
/
303. Range Sum Query - Immutable.cpp
60 lines (52 loc) · 1.63 KB
/
303. Range Sum Query - Immutable.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//Brute Force
//query time: O(n), space: O(1)
//Runtime: 176 ms, faster than 15.17% of C++ online submissions for Range Sum Query - Immutable.
//Memory Usage: 17.3 MB, less than 72.41% of C++ online submissions for Range Sum Query - Immutable.
class NumArray {
public:
vector<int> nums;
NumArray(vector<int>& nums) {
this->nums = nums;
}
int sumRange(int i, int j) {
int ans = 0;
for(int pos = i; pos <= j; pos++){
ans += nums[pos];
}
return ans;
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(i,j);
*/
//Cache
//Runtime: 28 ms, faster than 94.08% of C++ online submissions for Range Sum Query - Immutable.
//Memory Usage: 17.2 MB, less than 79.31% of C++ online submissions for Range Sum Query - Immutable.
//acc_sum[0] is 0
//acc_sum[k] is the cumulative sum for nums[0 ... k-1](inclusive)
//pre-computation time: O(n), query time: O(1)
//space: O(n)
class NumArray {
public:
vector<int> acc_sum;
NumArray(vector<int>& nums) {
int N = nums.size();
this->acc_sum = vector<int>(N+1);
//for padding
this->acc_sum[0] = 0;
for(int i = 1; i <= N; i++){
this->acc_sum[i] = this->acc_sum[i-1] + nums[i-1];
}
}
int sumRange(int i, int j) {
//convert i and j from 0-based to 1-based
return this->acc_sum[j+1] - this->acc_sum[i];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(i,j);
*/