Range Sum Query – Mutable – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an integer array nums
, handle multiple queries of the following types:
- Update the value of an element in
nums
. - Calculate the sum of the elements of
nums
between indicesleft
andright
inclusive whereleft <= right
.
Implement the NumArray
class:
NumArray(int[] nums)
Initializes the object with the integer arraynums
.void update(int index, int val)
Updates the value ofnums[index]
to beval
.int sumRange(int left, int right)
Returns the sum of the elements ofnums
between indicesleft
andright
inclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]
).
Example 1:
Input ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] Output [null, 9, null, 8] Explanation NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1, 2, 5] numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
- At most
3 * 104
calls will be made toupdate
andsumRange
.
C++ Range Sum Query – Mutable LeetCode Solution
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;
}
};
Java Range Sum Query – Mutable LeetCode Solution
public class NumArray {
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);
}
}
Python 3 Range Sum Query – Mutable LeetCode Solution
class NumArray(object):
def __init__(self, nums):
self.update = nums.__setitem__
self.sumRange = lambda i, j: sum(nums[i:j+1])
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below