307. Range Sum Query - Mutable

  • 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
2
3
4
5
6
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. 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


https://discuss.leetcode.com/topic/29939/c-solution-using-buckets-o-1-for-updating-and-o-n-0-5-for-query-in-the-worst-case-not-the-fast

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
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
61
62
63
64
65
66
67
68
69
70
71
class NumArray {
public:

struct Bucket
{
int sum;
vector<int> val;
};

int bucketNum;
int bucketSize;
vector<Bucket> Bs;

NumArray(vector<int> &nums) {
int size = nums.size();
int bucketNum = (int)sqrt(2*size);
bucketSize = bucketNum/2;
while(bucketSize * bucketNum<size) ++bucketSize;

Bs.resize(bucketNum);
for(int i=0, k=0; i<bucketNum; ++i)
{
int temp = 0;
Bs[i].val.resize(bucketSize);
for(int j=0; j<bucketSize && k<size; ++j, ++k)
{
temp += nums[k];
Bs[i].val[j] = nums[k];
}
Bs[i].sum = temp;
}
}

void update(int i, int val) {
int x = i / bucketSize;
int y = i % bucketSize;
Bs[x].sum += (val - Bs[x].val[y]);
Bs[x].val[y] = val;
}

int sumRange(int i, int j) {
int x1 = i / bucketSize;
int y1 = i % bucketSize;
int x2 = j / bucketSize;
int y2 = j % bucketSize;
int sum = 0;

if(x1==x2)
{
for(int a=y1; a<=y2; ++a)
{
sum += Bs[x1].val[a];
}
return sum;
}

for(int a=y1; a<bucketSize; ++a)
{
sum += Bs[x1].val[a];
}
for(int a=x1+1; a<x2; ++a)
{
sum += Bs[a].sum;
}
for(int b=0; b<=y2; ++b)
{
sum += Bs[x2].val[b];
}
return sum;
}
};

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
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
61
62
63
64
65
66
67
struct SegmentTreeNode {
int start, end, sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int a, int b):start(a),end(b),sum(0),left(nullptr),right(nullptr){}
};
class NumArray {
SegmentTreeNode* root;
public:
NumArray(vector<int> &nums) {
int n = nums.size();
root = buildTree(nums,0,n-1);
}

void update(int i, int val) {
modifyTree(i,val,root);
}

int sumRange(int i, int j) {
return queryTree(i, j, root);
}
SegmentTreeNode* buildTree(vector<int> &nums, int start, int end) {
if(start > end) return nullptr;
SegmentTreeNode* root = new SegmentTreeNode(start,end);
if(start == end) {
root->sum = nums[start];
return root;
}
int mid = start + (end - start) / 2;
root->left = buildTree(nums,start,mid);
root->right = buildTree(nums,mid+1,end);
root->sum = root->left->sum + root->right->sum;
return root;
}
int modifyTree(int i, int val, SegmentTreeNode* root) {
if(root == nullptr) return 0;
int diff;
if(root->start == i && root->end == i) {
diff = val - root->sum;
root->sum = val;
return diff;
}
int mid = (root->start + root->end) / 2;
if(i > mid) {
diff = modifyTree(i,val,root->right);
} else {
diff = modifyTree(i,val,root->left);
}
root->sum = root->sum + diff;
return diff;
}
int queryTree(int i, int j, SegmentTreeNode* root) {
if(root == nullptr) return 0;
if(root->start == i && root->end == j) return root->sum;
int mid = (root->start + root->end) / 2;
if(i > mid) return queryTree(i,j,root->right);
if(j <= mid) return queryTree(i,j,root->left);
return queryTree(i,mid,root->left) + queryTree(mid+1,j,root->right);
}
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

https://discuss.leetcode.com/topic/34585/strongly-recommend-for-beginners-clean-c-implementation-with-detailed-explaination

[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
2
3
4
5
num=a1b

-num= (a1b)¯ + 1 = a¯0b¯ + 1

-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b.

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Returns sum of arr[0..index] using BITree[0..n].  It assumes that

// BITree[] is constructed for given array arr[0..n-1]

1) Initialize sum as 0 and index as index+1.

2) Do following while index is greater than 0.

...a) Add BITree[index] to sum

...b) Go to parent of BITree[index]. Parent can be obtained by removing

the last set bit from index, i.e., index = index - (index & (-index))

3) Return sum.

Key ideas -2- update-value-function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
update(index, val): Updates BIT for operation arr[index] += val

// Note that arr[] is not changed here. It changes

// only BI Tree for the already made change in arr[].

1) Initialize index as index+1.

2) Do following while index is smaller than or equal to n.

...a) Add value to BITree[index]

...b) Go to parent of BITree[index]. Parent can be obtained by removing

the last set bit from index, i.e., index = index + (index & (-index))

Here is my final implementation.

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
class NumArray {
private:
vector<int> _nums;
vector<int> bit;

int lower_bit(int i){
return i&-i;
}

int query(int i){
i++;
int sum=0;
while(i>0){
sum+=bit[i];
i-=lower_bit(i);
}
return sum;
}

void add(int i, int val){
i++;
while(i<bit.size()){
bit[i]+=val;
i+=lower_bit(i);
}
}

public:
NumArray(vector<int> &nums) : _nums(nums) {
bit.resize(nums.size()+1);
for(int i=0; i<nums.size(); i++){
add(i, nums[i]);
}
}

void update(int i, int val) {
if(val!=_nums[i]){
add(i, val-_nums[i]);
_nums[i]=val;
}
}

int sumRange(int i, int j) {
return query(j)-query(i-1);
}
};

python


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

“0 lines” Python

1
2
3
4
class NumArray(object):
def __init__(self, nums):
self.update = nums.__setitem__
self.sumRange = lambda i, j: sum(nums[i:j+1])

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
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
class NumArray(object):
def __init__(self, nums):
self.n = len(nums)
self.a, self.c = nums, [0] * (self.n + 1)
for i in range(self.n):
k = i + 1
while k <= self.n:
self.c[k] += nums[i]
k += (k & -k)

def update(self, i, val):
diff, self.a[i] = val - self.a[i], val
i += 1
while i <= self.n:
self.c[i] += diff
i += (i & -i)

def sumRange(self, i, j):
res, j = 0, j + 1
while j:
res += self.c[j]
j -= (j & -j)
while i:
res -= self.c[i]
i -= (i & -i)
return res

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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
"""
The idea here is to build a segment tree. Each node stores the left and right
endpoint of an interval and the sum of that interval. All of the leaves will store
elements of the array and each internal node will store sum of leaves under it.
Creating the tree takes O(n) time. Query and updates are both O(log n).
"""

#Segment tree node
class Node(object):
def __init__(self, start, end):
self.start = start
self.end = end
self.total = 0
self.left = None
self.right = None


class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
#helper function to create the tree from input array
def createTree(nums, l, r):

#base case
if l > r:
return None

#leaf node
if l == r:
n = Node(l, r)
n.total = nums[l]
return n

mid = (l + r) // 2

root = Node(l, r)

#recursively build the Segment tree
root.left = createTree(nums, l, mid)
root.right = createTree(nums, mid+1, r)

#Total stores the sum of all leaves under root
#i.e. those elements lying between (start, end)
root.total = root.left.total + root.right.total

return root

self.root = createTree(nums, 0, len(nums)-1)

def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: int
"""
#Helper function to update a value
def updateVal(root, i, val):

#Base case. The actual value will be updated in a leaf.
#The total is then propogated upwards
if root.start == root.end:
root.total = val
return val

mid = (root.start + root.end) // 2

#If the index is less than the mid, that leaf must be in the left subtree
if i <= mid:
updateVal(root.left, i, val)

#Otherwise, the right subtree
else:
updateVal(root.right, i, val)

#Propogate the changes after recursive call returns
root.total = root.left.total + root.right.total

return root.total

return updateVal(self.root, i, val)

def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
#Helper function to calculate range sum
def rangeSum(root, i, j):

#If the range exactly matches the root, we already have the sum
if root.start == i and root.end == j:
return root.total

mid = (root.start + root.end) // 2

#If end of the range is less than the mid, the entire interval lies
#in the left subtree
if j <= mid:
return rangeSum(root.left, i, j)

#If start of the interval is greater than mid, the entire inteval lies
#in the right subtree
elif i >= mid + 1:
return rangeSum(root.right, i, j)

#Otherwise, the interval is split. So we calculate the sum recursively,
#by splitting the interval
else:
return rangeSum(root.left, i, mid) + rangeSum(root.right, mid+1, j)

return rangeSum(self.root, i, j)



# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.update(1, 10)
# numArray.sumRange(1, 2)

java


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

17 ms Java solution with segment tree

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public class NumArray {

class SegmentTreeNode {
int start, end;
SegmentTreeNode left, right;
int sum;

public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.left = null;
this.right = null;
this.sum = 0;
}
}

SegmentTreeNode root = null;

public NumArray(int[] nums) {
root = buildTree(nums, 0, nums.length-1);
}

private SegmentTreeNode buildTree(int[] nums, int start, int end) {
if (start > end) {
return null;
} else {
SegmentTreeNode ret = new SegmentTreeNode(start, end);
if (start == end) {
ret.sum = nums[start];
} else {
int mid = start + (end - start) / 2;
ret.left = buildTree(nums, start, mid);
ret.right = buildTree(nums, mid + 1, end);
ret.sum = ret.left.sum + ret.right.sum;
}
return ret;
}
}

void update(int i, int val) {
update(root, i, val);
}

void update(SegmentTreeNode root, int pos, int val) {
if (root.start == root.end) {
root.sum = val;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (pos <= mid) {
update(root.left, pos, val);
} else {
update(root.right, pos, val);
}
root.sum = root.left.sum + root.right.sum;
}
}

public int sumRange(int i, int j) {
return sumRange(root, i, j);
}

public int sumRange(SegmentTreeNode root, int start, int end) {
if (root.end == end && root.start == start) {
return root.sum;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (end <= mid) {
return sumRange(root.left, start, end);
} else if (start >= mid+1) {
return sumRange(root.right, start, end);
} else {
return sumRange(root.right, mid+1, end) + sumRange(root.left, start, mid);
}
}
}
}

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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class NumArray {
/**
* Binary Indexed Trees (BIT or Fenwick tree):
* https://www.topcoder.com/community/data-science/data-science-
* tutorials/binary-indexed-trees/
*
* Example: given an array a[0]...a[7], we use a array BIT[9] to
* represent a tree, where index [2] is the parent of [1] and [3], [6]
* is the parent of [5] and [7], [4] is the parent of [2] and [6], and
* [8] is the parent of [4]. I.e.,
*
* BIT[] as a binary tree:
* ______________*
* ______*
* __* __*
* * * * *
* indices: 0 1 2 3 4 5 6 7 8
*
* BIT[i] = ([i] is a left child) ? the partial sum from its left most
* descendant to itself : the partial sum from its parent (exclusive) to
* itself. (check the range of "__").
*
* Eg. BIT[1]=a[0], BIT[2]=a[1]+BIT[1]=a[1]+a[0], BIT[3]=a[2],
* BIT[4]=a[3]+BIT[3]+BIT[2]=a[3]+a[2]+a[1]+a[0],
* BIT[6]=a[5]+BIT[5]=a[5]+a[4],
* BIT[8]=a[7]+BIT[7]+BIT[6]+BIT[4]=a[7]+a[6]+...+a[0], ...
*
* Thus, to update a[1]=BIT[2], we shall update BIT[2], BIT[4], BIT[8],
* i.e., for current [i], the next update [j] is j=i+(i&-i) //double the
* last 1-bit from [i].
*
* Similarly, to get the partial sum up to a[6]=BIT[7], we shall get the
* sum of BIT[7], BIT[6], BIT[4], i.e., for current [i], the next
* summand [j] is j=i-(i&-i) // delete the last 1-bit from [i].
*
* To obtain the original value of a[7] (corresponding to index [8] of
* BIT), we have to subtract BIT[7], BIT[6], BIT[4] from BIT[8], i.e.,
* starting from [idx-1], for current [i], the next subtrahend [j] is
* j=i-(i&-i), up to j==idx-(idx&-idx) exclusive. (However, a quicker
* way but using extra space is to store the original array.)
*/

int[] nums;
int[] BIT;
int n;

public NumArray(int[] nums) {
this.nums = nums;

n = nums.length;
BIT = new int[n + 1];
for (int i = 0; i < n; i++)
init(i, nums[i]);
}

public void init(int i, int val) {
i++;
while (i <= n) {
BIT[i] += val;
i += (i & -i);
}
}

void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
init(i, diff);
}

public int getSum(int i) {
int sum = 0;
i++;
while (i > 0) {
sum += BIT[i];
i -= (i & -i);
}
return sum;
}

public int sumRange(int i, int j) {
return getSum(j) - getSum(i - 1);
}
}

// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);
谢谢你,可爱的朋友。