- 19.1%

https://leetcode.com/problems/range-sum-query-mutable/?tab=Description

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.

1 | Example: |

Note:

- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.

leetcode官方答案

https://leetcode.com/articles/range-sum-query-mutable/

#### cpp

C++ solution using “buckets”. O(1) for updating and O(n^0.5) for query in the worst case (not the fast).

The idea is using “buckets”. Assume the length of the input array is n, we can partition the whole array into m buckets, with each bucket having k=n/m elements. For each bucket, we record two kind of information: 1) a copy of elements in the bucket, 2) the sum of all the elements in the bucket.

For example: If the input is [0,1,2,3,4,5,6,7,8,9], and we partition it into 4 buckets, formatted as {[numbers], sum}:

bucket0: {[0, 1, 2], 3}

bucket1: {[3, 4, 5], 12}

bucket2: {[6, 7, 8], 21}

bucket3: {[9], 9};

Updating is easy. You just need to find the right bucket, modify the element value, and change the “sum” value in that bucket accordingly. The operation takes O(1) time.

Summation is a little complicated. In the above example, let’s say we want to compute the sum in range [1, 7]. We can see, the numbers we want to accumulate are in bucket0, bucket1, and bucket2. Specifically, we only need parts of numbers in bucket0 and bucket2, and all the numbers in bucket1. Because the summation of all numbers in bucket1 have already been computed, we don’t need to compute it again. So, instead of doing (1+2) + (3+4+5) + (6+7), we can just do (1+2) + 12 + (6+7). We save two “+” operations. If you change the size of buckets, the number of saved “+” operations will be different. The questions is:

What is the best size that can save the most “+” operations?

Here is my analysis, which might be incorrect.

We have:

The number of buckets is m.

The size of each bucket is k.

The length of input array is n, and we have mk=n.

In the worst case (the query is [0, n-1]), we will first add all the elements in bucket0, then add from bucket1 to bucket(m-2), and finally add all the elements in bucket(m-1), so we do 2k+m-2 “+” operations. We want to find the minimum value of 2k+m. Because 2km=2n, when 2k=m, 2k+m reaches the minimum value. (Need proof?) So we have m = sqrt(2n) and k=sqrt(n/2).

Therefore, in the worst case, the best size of bucket is k=sqrt(n/2), and the complexity is O(2k+m-2)=O(2m-2)=O(m)=O(sqrt(2n))=O(n^0.5);

Thank you for pointing out any mistake!

1 | class NumArray { |

https://discuss.leetcode.com/topic/30120/c-segment-tree-update-and-sum-are-both-o-logn

C++, Segment Tree,update and sum are both O(logn)

1 | struct SegmentTreeNode { |

[strongly recommend for beginners]clean C++ implementation with detailed explaination

Similiar C++ implementation based others’ posts.

I have refered to the post from GeekForGeek

http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

I think the key points are that you should set “i++” and understand the relationship of the children and parents.

THE KEY POINTS

idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx (look at the Table 1.1 for clarification). We also write that idx is responsible for indexes from (idx - 2^r + 1) to idx (note that responsibility is the key in our algorithm and is the way of manipulating the tree).

FOR EXAMPLE

Suppose we are looking for cumulative frequency of index 13 (for the first 13 elements). In binary notation, 13 is equal to 1101. Accordingly, we will calculate

1 | c[1101] = tree[1101] + tree[1100] + tree[1000] |

HOW TO GET THE FINAL LAST SET BIT

There are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.

1 | num=a1b |

b consists of all zeroes, so b¯ consists of all ones. Finally we have

1 | so the last set bit : 00..1...00 = num & -num |

Key ideas -1-

get-function-details

getSum(index): Returns sum of arr[0..index]

1 | // Returns sum of arr[0..index] using BITree[0..n]. It assumes that |

Key ideas -2- update-value-function

1 | update(index, val): Updates BIT for operation arr[index] += val |

Here is my final implementation.

1 | class NumArray { |

#### python

https://discuss.leetcode.com/topic/30016/0-lines-python

“0 lines” Python

1 | class NumArray(object): |

I added two lines, but I also removed two lines, so zero overall, right? Just kidding :-P

Not a serious solution, just showing some Python trickery. The sumRange takes linear time, but due to the test suite being weak, this solution gets accepted (in about 1200-1300ms).

https://discuss.leetcode.com/topic/33747/148ms-python-solution-binary-indexed-tree

148ms Python solution, Binary Indexed Tree

Use self.c to represent Binary Indexed Tree. Section sums are stored in self.c[1..len(nums)]. x & -x is lowbit function, which will return x’s rightmost bit 1, e.g. lowbit(7) = 1, lowbit(20) = 4.

self.c[1] = nums[0]

self.c[2] = nums[0] + nums[1]

self.c[3] = nums[2]

self.c[4] = nums[0] + nums[1] + nums[2] + nums[3]

self.c[5] = nums[4]

self.c[6] = nums[4] + nums[5]

self.c[7] = nums[6]

self.c[8] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5] + nums[6] + nums[7]

1 | class NumArray(object): |

https://discuss.leetcode.com/topic/45266/python-well-commented-solution-using-segment-trees

Python: Well commented solution using Segment Trees

This solution is based on the top voted solution by 2guotou, which is in Java.

1 | """ |

#### java

https://discuss.leetcode.com/topic/29918/17-ms-java-solution-with-segment-tree

17 ms Java solution with segment tree

1 | public class NumArray { |

https://discuss.leetcode.com/topic/31599/java-using-binary-indexed-tree-with-clear-explanation

Java using Binary Indexed Tree with clear explanation

This is to share the explanation of the BIT and the meaning of the bit operations.

1 | public class NumArray { |