This problem looks busy at first, but the accepted solution is built around one steady invariant. For 307. Range Sum Query - Mutable Medium, the solution in this repository is mainly a data structure design solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design, binary search, two pointers, sliding window.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are update, sumRange, buildTree, merge, buildSegTree.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: preprocessing - O(n), range sum query - O(sqrt(n)), update query - O(1)
- Space: O(sqrt(n))
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 516 ms, faster than 5.03% of C++ online submissions for Range Sum Query - Mutable.
02//Memory Usage: 16.5 MB, less than 100.00% of C++ online submissions for Range Sum Query - Mutable.
03class NumArray {
04public:
05 vector<int> nums;
06 vector<int> sum;
07
08 NumArray(vector<int>& nums) {
09 this->nums = nums;
10 this->sum = vector<int>(nums.size(), 0);
11 for(int i = 0; i < nums.size(); i++){
12 sum[i] = ((i-1>=0)?sum[i-1]:0) + nums[i];
13 }
14 }
15
16 void update(int i, int val) {
17 for(int cur = i; cur < sum.size(); cur++){
18 sum[cur] += (val - nums[i]);
19 }
20 nums[i] = val;
21 }
22
23 int sumRange(int i, int j) {
24 return sum[j] - ((i-1>=0)?sum[i-1]:0);
25 }
26};
27
28/**
29 * Your NumArray object will be instantiated and called as such:
30 * NumArray* obj = new NumArray(nums);
31 * obj->update(i,val);
32 * int param_2 = obj->sumRange(i,j);
33 */
34
35//Approach 2: Sqrt Decomposition
36//Runtime: 52 ms, faster than 38.63% of C++ online submissions for Range Sum Query - Mutable.
37//Memory Usage: 16.6 MB, less than 100.00% of C++ online submissions for Range Sum Query - Mutable.
38//time: preprocessing - O(n), range sum query - O(sqrt(n)), update query - O(1)
39//space: O(sqrt(n))
40class NumArray {
41public:
42 vector<int> blocks;
43 vector<int> nums;
44 int len;
45
46 NumArray(vector<int>& nums) {
47 this->nums = nums;
48 /*
49 9 -> 3
50 10 -> 4
51 */
52 if(nums.size() == 0){
53 this->len = 0;
54 }else{
55 this->len = ceil(nums.size()/sqrt(nums.size()));
56 }
57 this->blocks = vector<int>(len, 0);
58 for(int i = 0; i < nums.size(); i++){
59 blocks[i/len] += nums[i];
60 }
61 }
62
63 void update(int i, int val) {
64 int blockId = i/len;
65 blocks[blockId] += (val - nums[i]);
66 nums[i] = val;
67 }
68
69 int sumRange(int i, int j) {
70 int sum = 0;
71
72 int startBlock = i/len, endBlock = j/len;
73
74 if(startBlock == endBlock){
75 for(int k = i; k <= j; k++){
76 sum += nums[k];
77 }
78 }else{
79 /*
80 startBlock+1: the next block's id
81 (startBlock+1)*len: the next block's start position
82 (startBlock+1)*len-1: the current block's end position
83 */
84 for(int k = i; k <= (startBlock+1)*len -1; k++){
85 sum += nums[k];
86 }
87 for(int k = startBlock+1; k <= endBlock-1; k++){
88 sum += blocks[k];
89 }
90 for(int k = endBlock*len; k <= j; k++){
91 sum += nums[k];
92 }
93 }
94
95 return sum;
96 }
97};
98
99//Approach 3: Segment Tree, iterative version
100//tree[0] is not used in this implementation, only tree[1...2n-1] are meaningful
101//Runtime: 44 ms, faster than 50.75% of C++ online submissions for Range Sum Query - Mutable.
102//Memory Usage: 16.7 MB, less than 100.00% of C++ online submissions for Range Sum Query - Mutable.
103//Build segment tree - time O(n), space O(n)
104//Update segment tree - time O(logn), space O(1)
105//Range Sum Query - time O(logn), space O(1)
106class NumArray {
107public:
108 vector<int> tree;
109 int n;
110
111 NumArray(vector<int>& nums) {
112 if(nums.size() > 0){
113 n = nums.size();
114 buildTree(nums);
115 }
116 }
117
118 void buildTree(vector<int>& nums){
119 tree = vector<int>(n*2);
120 //tree[n ... 2n-1] = nums[0 ... n-1]
121 for(int i = n, j = 0; i < n*2; i++, j++){
122 tree[i] = nums[j];
123 }
124 /*
125 tree[n-1] = tree[2n-2] + tree[2n-1]
126 if n = 8
127 tree[7] = tree[14] + tree[15]
128 tree[6] = tree[12] + tree[13]
129 tree[5] = tree[10] + tree[11]
130 tree[4] = tree[8] + tree[9]
131
132 tree[3] = tree[6] + tree[7]
133 tree[2] = tree[4] + tree[5]
134
135 tree[1] = tree[2] + tree[3]
136
137 if n = 3
138 tree[2] = tree[4] + tree[5]
139 tree[1] = tree[2] + tree[3] //total sum of leaves
140 */
141 //note that tree[0] is meaningless
142 for(int i = n-1; i > 0; i--){
143 tree[i] = tree[i*2] + tree[i*2+1];
144 }
145 };
146
147 void update(int i, int val) {
148 //recall that the leaf node takes tree[n ... 2n-1]
149 i += n; //i is the index of nums, i+n is the index of tree
150 tree[i] = val;
151 //note that tree[0] is meaningless
152 //update tree[i]'s ancestor up to root
153 while(i > 0){
154 /*
155 here we want to find current node and its sibling
156
157 current node is either left or right child of its parent,
158 we can check it by "i%2 == 0",
159 it "i" is even, current node is left child of its parent,
160 so its sibling is its parent's right child
161 */
162 int left = i;
163 int right = i;
164 if(i % 2 == 0){
165 //tree[i] is left child of its parent
166 //its sibling tree[i+1] is right child of its parent
167 right = i+1;
168 }else{
169 //it's right node
170 left = i-1;
171 }
172 //update parent
173 tree[i/2] = tree[left] + tree[right];
174 i /= 2;
175 }
176 }
177
178 int sumRange(int i, int j){
179 //recall that the leaf node takes tree[n ... 2n-1]
180 i += n; //converts to index of tree
181 j += n;
182
183 int sum = 0;
184
185 while(i <= j){ // the range [i, j] is inclusive on both sides
186 // cout << "[" << i << ", " << j << "]" << endl;
187 if(i % 2 == 1){
188 /*
189 if i is right child of its parent,
190 then we cannot use its parent's value,
191 so we have nothing but to directly add "tree[i]" onto "sum"
192 */
193 // cout << "l: " << i << endl;
194 sum += tree[i];
195 /*
196 after adding "tree[i]",
197 we will go to its right neighbor,
198 and then go up to its parent
199 (note that tree[i] and tree[i+1]'s parents are different)
200 */
201 i++;
202 }
203 if(j % 2 == 0){
204 /*
205 if r is left child of its parent,
206 then we cannot use its parent's value,
207 so we have nothing but to directly add "tree[j]" onto "sum"
208 */
209 // cout << "r: " << j << endl;
210 sum += tree[j];
211 /*
212 we will go to its left neighbor,
213 and then go up to its parent
214 (note that tree[j] and tree[j-1]'s parents are different)
215 */
216 j--;
217 }
218 i /= 2;
219 j /= 2;
220 }
221
222 return sum;
223 }
224};
225
226/**
227 * Your NumArray object will be instantiated and called as such:
228 * NumArray* obj = new NumArray(nums);
229 * obj->update(i,val);
230 * int param_2 = obj->sumRange(i,j);
231 */
232
233//Segment tree, recursive version
234//https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/
235//Runtime: 44 ms, faster than 50.75% of C++ online submissions for Range Sum Query - Mutable.
236//Memory Usage: 17 MB, less than 100.00% of C++ online submissions for Range Sum Query - Mutable.
237//Build segment tree - time O(n), space O(n)
238//Update segment tree - time O(logn), space O(1)
239//Range Sum Query - time O(logn), space O(1)
240class NumArray {
241public:
242 vector<int> tree;
243 int n;
244
245 int merge(int a, int b){
246 return a+b;
247 }
248
249 void buildSegTree(vector<int>& arr, int treeIndex, int lo, int hi){
250 if(lo == hi){
251 //leaf node
252 tree[treeIndex] = arr[lo];
253 return;
254 }
255
256 int mid = (lo + hi)/2;
257 //the tree node "treeIndex*2+1" represents for the range [lo,mid]
258 buildSegTree(arr, treeIndex*2+1, lo, mid);
259 //the tree node "treeIndex*2+2" represents for the range [mid+1,hi]
260 buildSegTree(arr, treeIndex*2+2, mid+1, hi);
261
262 tree[treeIndex] = merge(tree[treeIndex*2+1], tree[treeIndex*2+2]);
263 };
264
265 int querySegTree(int treeIndex, int lo, int hi, int i, int j){
266 // cout << "treeIndex: " << treeIndex << ", lo: " << lo << ", hi: " << hi << ", i: " << i << ", j: " << j << endl;
267 /*
268 query for arr[i ... j]
269 we are currently at the tree node "treeIndex",
270 and this tree node's range is arr[lo ... hi]
271 lo, hi, i, j are all index of arr
272 treeIndex is index of tree
273 */
274 if(lo > j || hi < i){
275 //the part we are looking has no intersection with arr[i...j]
276 return 0;
277 }
278
279 if(i <= lo && hi <= j){
280 //tree[treeIndex] is inside [i...j]
281 return tree[treeIndex];
282 }
283
284 int mid = (lo+hi)/2;
285
286 // cout << "mid: " << mid << endl;
287
288 //when the query range falls into either left or right part of current subtree
289 if(i > mid){
290 // cout << "i > mid, go right" << endl;
291 //the query range is completely in right subtree
292 //find in right subtree, which represents for range [mid+1,hi]
293 //directly return!
294 return querySegTree(treeIndex*2+2, mid+1, hi, i, j);
295 }else if(j <= mid){
296 // cout << "j <= mid, go left" << endl;
297 //the query range is completely in left subtree
298 //find in left subtree, which represents for range [lo,mid]
299 //directly return!
300 return querySegTree(treeIndex*2+1, lo, mid, i, j);
301 }
302
303 //the query range cross the middle point of current subtree
304 //divide and conquer
305 //first query for left part
306 // cout << "leftQuery" << endl;
307 int leftQuery = querySegTree(treeIndex*2+1, lo, mid, i, mid);
308 //and then query for right part
309 // cout << "rightQuery" << endl;
310 int rightQuery = querySegTree(treeIndex*2+2, mid+1, hi, mid+1, j);
311
312 return merge(leftQuery, rightQuery);
313 };
314
315 void updateValSegTree(int treeIndex, int lo, int hi, int arrayIndex, int val){
316 // cout << "treeIndex: " << treeIndex << ", lo: " << lo << ", hi: " << hi << endl;
317 if(lo == hi){
318 //leaf node, directly update
319 tree[treeIndex] = val;
320 return;
321 }
322
323 int mid = (lo + hi)/2;
324
325 //update its child
326 if(arrayIndex > mid){
327 //the element to be updated(arr[arrayIndex]) is in right subtree
328 updateValSegTree(treeIndex*2+2, mid+1, hi, arrayIndex, val);
329 }else{
330 //the element to be updated(arr[arrayIndex]) is in left subtree
331 updateValSegTree(treeIndex*2+1, lo, mid, arrayIndex, val);
332 }
333
334 //current node needs to be updated, too!
335 tree[treeIndex] = merge(tree[treeIndex*2+1], tree[treeIndex*2+2]);
336 };
337
338 NumArray(vector<int>& nums) {
339 n = nums.size();
340 if(n > 0){
341 //A segment tree for an nn element range can be comfortably represented using an array of size is approximately 4∗n.
342 tree = vector<int>(4*n, 0);
343 /*
344 index 0 is meaningful here!
345 */
346 buildSegTree(nums, 0, 0, n-1);
347 // for(int i = 0; i < 4*n; i++){
348 // cout << tree[i] << " ";
349 // }
350 // cout << endl;
351 }
352 }
353
354 void update(int i, int val) {
355 updateValSegTree(0, 0, n-1, i, val);
356 }
357
358 int sumRange(int i, int j) {
359 // cout << endl << "query " << i << ", " << j << endl;
360 int sum = querySegTree(0, 0, n-1, i, j);
361 // cout << endl;
362 return sum;
363 }
364};
365
366/**
367 * Your NumArray object will be instantiated and called as such:
368 * NumArray* obj = new NumArray(nums);
369 * obj->update(i,val);
370 * int param_2 = obj->sumRange(i,j);
371 */
372
373//Binary Indexed Tree
374//https://leetcode.com/problems/range-sum-query-mutable/discuss/75753/Java-using-Binary-Indexed-Tree-with-clear-explanation
375//https://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a
376//Runtime: 48 ms, faster than 46.27% of C++ online submissions for Range Sum Query - Mutable.
377//Memory Usage: 16.7 MB, less than 100.00% of C++ online submissions for Range Sum Query - Mutable.
378class NumArray {
379public:
380 /**
381 * Binary Indexed Trees (BIT or Fenwick tree):
382 * https://www.topcoder.com/community/data-science/data-science-
383 * tutorials/binary-indexed-trees/
384 *
385 * Example: given an array a[0]...a[7], we use a array BIT[9] to
386 * represent a tree, where index [2] is the parent of [1] and [3], [6]
387 * is the parent of [5] and [7], [4] is the parent of [2] and [6], and
388 * [8] is the parent of [4]. I.e.,
389 *
390 * BIT[] as a binary tree:
391 * ______________*
392 * ______*
393 * __* __*
394 * * * * *
395 * indices: 0 1 2 3 4 5 6 7 8
396 *
397 * BIT[i] = ([i] is a left child) ? the partial sum from its left most
398 * descendant to itself : the partial sum from its parent (exclusive) to
399 * itself. (check the range of "__").
400 *
401 * Eg. BIT[1]=a[0], BIT[2]=a[1]+BIT[1]=a[1]+a[0], BIT[3]=a[2],
402 * BIT[4]=a[3]+BIT[3]+BIT[2]=a[3]+a[2]+a[1]+a[0],
403 * BIT[6]=a[5]+BIT[5]=a[5]+a[4],
404 * BIT[8]=a[7]+BIT[7]+BIT[6]+BIT[4]=a[7]+a[6]+...+a[0], ...
405 *
406 * Thus, to update a[1]=BIT[2], we shall update BIT[2], BIT[4], BIT[8],
407 * i.e., for current [i], the next update [j] is j=i+(i&-i) //double the
408 * last 1-bit from [i].
409 *
410 * Similarly, to get the partial sum up to a[6]=BIT[7], we shall get the
411 * sum of BIT[7], BIT[6], BIT[4], i.e., for current [i], the next
412 * summand [j] is j=i-(i&-i) // delete the last 1-bit from [i].
413 *
414 * To obtain the original value of a[7] (corresponding to index [8] of
415 * BIT), we have to subtract BIT[7], BIT[6], BIT[4] from BIT[8], i.e.,
416 * starting from [idx-1], for current [i], the next subtrahend [j] is
417 * j=i-(i&-i), up to j==idx-(idx&-idx) exclusive. (However, a quicker
418 * way but using extra space is to store the original array.)
419 */
420
421 /*
422 if using 2's complement,
423 +a + (-a) will be 0,
424 and "-a" is attained by
425 reverting all bits of "+a"
426 and then add 1 onto it
427
428 if a = 6,
429 a = 110,
430 -a = 001+1 = 010
431 a & (-a) = 010,
432 so we get least significant bit
433 */
434
435 vector<int> nums;
436 vector<int> BIT;
437 int n;
438
439 void init(int i, int val){
440 /*
441 the argument i is the index of "nums",
442 adding 1 converts it to the index of "BIT"
443 */
444 i++;
445 /*
446 BIT[0] is meaningless,
447 BIT[1-n] is meaningful
448 */
449 // cout << "init: ";
450 while(i <= n){
451 // cout << i << " ";
452 BIT[i] += val;
453 //double least significant bit
454 /*
455 current node is next node's left child or grandson,
456 so next node's value should contain current node's value
457 */
458 //go to its parent
459 i += (i&-i);
460 }
461 // cout << endl;
462 };
463
464 NumArray(vector<int>& nums) {
465 this->nums = nums;
466 n = nums.size();
467 /*
468 different from segment tree
469 which requires n*4 space,
470 it only needs n+1 space!!
471 */
472 BIT = vector<int>(n+1);
473 for(int i = 0; i < n; i++){
474 init(i, nums[i]);
475 }
476
477 // cout << "BIT: ";
478 // for(int i = 1; i <= n; i++){
479 // cout << BIT[i] << " ";
480 // }
481 // cout << endl;
482 }
483
484 void update(int i, int val) {
485 int diff = val - nums[i];
486 //update the data structure "nums"
487 nums[i] = val;
488 //update the data structure "BIT"
489 init(i, diff);
490 }
491
492 int getSum(int i){
493 //get sum of arr[0,i]
494 int sum = 0;
495
496 //convert from "nums" index to "BIT"'s index
497 i++;
498
499 // cout << "getSum: ";
500 //[1,n] are valid indices of "BIT"
501 while(i > 0){
502 // cout << i << " ";
503 sum += BIT[i];
504 //remove least significant bit
505 /*
506 current node is next node's right child or grandson,
507 so next node's value doesn't contain current node's value.
508 So to get cumulative sum, we should continue to add next node's value
509 */
510 //go to the node higher than and to the left of itself
511 i -= (i&-i);
512 }
513 // cout << endl;
514
515 return sum;
516 };
517
518 int sumRange(int i, int j) {
519 return getSum(j) - getSum(i-1);
520 }
521};
522
523/**
524 * Your NumArray object will be instantiated and called as such:
525 * NumArray* obj = new NumArray(nums);
526 * obj->update(i,val);
527 * int param_2 = obj->sumRange(i,j);
528 */Cost
Complexity
Time
preprocessing - O(n), range sum query - O(sqrt(n)), update query - O(1)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(sqrt(n))
Auxiliary state plus the answer structure where the problem requires one.