This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given an integer array *nums*, find the sum of the elements between indices *i* and *j* (*i* ≤ *j*), inclusive.

**Example:**

Given nums = [1, 3, 5] sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8

**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.

b'

\n## Summary

\n## Solution

\n#### Approach #1 (Naive) [Time Limit Exceeded]

\n\n#### Approach #2 (Sqrt decomposition) [Accepted]

\n\n#### Approach #3 (Segment tree) [Accepted]

\n##### 1. Build segment tree

\n\n##### 2. Update segment tree

\n\n##### 3. Range Sum Query

\n\n## Further Thoughts

\n

'
\n\n

\nThis article is for intermediate level readers. It introduces the following concepts:\nRange sum query, Sqrt decomposition, Segment tree.

\n**Algorithm**

A trivial solution for Range Sum Query - `RSQ(i, j)`

is to iterate the array from index to and sum each element.

**Java**

private int[] nums;\npublic int sumRange(int i, int j) {\n int sum = 0;\n for (int l = i; l <= j; l++) {\n sum += data[l];\n }\n return sum;\n}\n\npublic int update(int i, int val) {\n nums[i] = val;\n}\n// Time Limit Exceeded\n

**Complexity Analysis**

- \n
- \n
Time complexity : - range sum query, - update query

\nFor range sum query we access each element from the array for constant time and in the worst case we access elements. Therefore time complexity is . Time complexity of update query is .

\n \n - \n
Space complexity : .

\n \n

**Intuition**

The idea is to split the array in blocks with length of . Then we calculate the sum of each block and store it in auxiliary memory `b`

.\nTo query `RSQ(i, j)`

, we will add the sums of all the blocks lying inside and those that partially overlap with range .

**Algorithm**

*Figure 1. Range sum query using SQRT decomposition.*

In the example above, the array `nums`

\'s length is `9`

, which is split into blocks of size . To get `RSQ(1, 7)`

we add `b[1]`

. It stores the sum of `range [3, 5]`

and partially sums from `block 0`

and `block 2`

, which are overlapping boundary blocks.

**Java**

private int[] b;\nprivate int len;\nprivate int[] nums;\n\npublic NumArray(int[] nums) {\n this.nums = nums;\n double l = Math.sqrt(nums.length);\n len = (int) Math.ceil(nums.length/l);\n b = new int [len];\n for (int i = 0; i < nums.length; i++)\n b[i / len] += nums[i];\n}\n\npublic int sumRange(int i, int j) {\n int sum = 0;\n int startBlock = i / len;\n int endBlock = j / len;\n if (startBlock == endBlock) {\n for (int k = i; k <= j; k++)\n sum += nums[k];\n } else {\n for (int k = i; k <= (startBlock + 1) * len - 1; k++)\n sum += nums[k];\n for (int k = startBlock + 1; k <= endBlock - 1; k++)\n sum += b[k];\n for (int k = endBlock * len; k <= j; k++)\n sum += nums[k];\n }\n return sum;\n}\n\npublic void update(int i, int val) {\n int b_l = i / len;\n b[b_l] = b[b_l] - nums[i] + val;\n nums[i] = val;\n}\n// Accepted\n

**Complexity Analysis**

- \n
- \n
Time complexity : - preprocessing, - range sum query, - update query

\nFor range sum query in the worst-case scenario we have to sum approximately elements. In this case the range includes blocks, which total sum costs operations. In addition to this we have to add the sum of the two boundary blocks. This takes another operations. The total amount of operations is around .

\n \n - \n
Space complexity : .

\nWe need additional memory to store all block sums.

\n \n

**Algorithm**

Segment tree is a very flexible data structure, because it is used to solve numerous range query problems like finding minimum, maximum, sum, greatest common divisor, least common denominator in array in logarithmic time.

\n\n*Figure 2. Illustration of Segment tree.*

The segment tree for array is a binary tree in which each node contains **aggregate** information (min, max, sum, etc.) for a subrange of the array, as its left and right child hold information for range and .

Segment tree could be implemented using either an array or a tree. For an array implementation, if the element at index is not a leaf, its left and right child are stored at index and respectively.

\nIn the example above (Figure 2), every leaf node contains the initial array elements `{2,4,5,7,8,9}`

. The internal nodes contain the sum of the corresponding elements in range - `(11)`

for the elements from index 0 to index 2. The root `(35)`

being the sum of its children `(6)`

;`(29)`

, holds the total sum of the entire array.

Segment Tree can be broken down to the three following steps:

\n- \n
- Pre-processing step which builds the segment tree from a given array. \n
- Update the segment tree when an element is modified. \n
- Calculate the Range Sum Query using the segment tree. \n

We will use a very effective bottom-up approach to build segment tree. We already know from the above that if some node holds the sum of range, its left and right children hold the sum for range and respectively.

\nTherefore to find the sum of node , we need to calculate the sum of its right and left child in advance.

\nWe begin from the leaves, initialize them with input array elements . Then we move upward to the higher level to calculate the parents\' sum till we get to the root of the segment tree.

\n**Java**

int[] tree;\nint n;\npublic NumArray(int[] nums) {\n if (nums.length > 0) {\n n = nums.length;\n tree = new int[n * 2];\n buildTree(nums);\n }\n}\nprivate void buildTree(int[] nums) {\n for (int i = n, j = 0; i < 2 * n; i++, j++)\n tree[i] = nums[j];\n for (int i = n - 1; i > 0; --i)\n tree[i] = tree[i * 2] + tree[i * 2 + 1];\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nTime complexity is , because we calculate the sum of one node during each iteration of the for loop. There are approximately nodes in a segment tree.

\nThis could be proved in the following way: Segmented tree for array with elements has leaves (the array elements itself). The number of nodes in each level is half the number in the level below.

\nSo if we sum the number by level we will get:

\n\n\n

\n \n - \n
Space complexity : .

\nWe used extra space to store the segment tree.

\n \n

When we update the array at some index we need to rebuild the segment tree, because there are tree nodes which contain the sum of the modified element. Again we will use a bottom-up approach. We update the leaf node that stores . From there we will follow the path up to the root updating the value of each parent as a sum of its children values.

\n**Java**

void update(int pos, int val) {\n pos += n;\n tree[pos] = val;\n while (pos > 0) {\n int left = pos;\n int right = pos;\n if (pos % 2 == 0) {\n right = pos + 1;\n } else {\n left = pos - 1;\n }\n // parent is updated after child is updated\n tree[pos / 2] = tree[left] + tree[right];\n pos /= 2;\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : .

\nAlgorithm has time complexity, because there are a few tree nodes with range that include th array element, one on each level. There are levels.

\n \n - \n
Space complexity : .

\n \n

We can find range sum query using segment tree in the following way:

\nAlgorithm hold loop invariant:

\n\n and sum of and has been calculated, where and are the left and right boundary of calculated sum.\nInitially we set with left leaf and with right leaf .\nRange shrinks on each iteration till range borders meets after approximately iterations of the algorithm

\n- \n
- Loop till \n
- \n
- Check if is right child of its parent \n
- \n
- \n is right child of . Then contains sum of range of and another child which is outside the range and we don\'t need parent sum. Add to without its parent and set to point to the right of on the upper level. \n
- \n is not right child of . Then parent contains sum of range which lies in . Add to and set to point to the parent of \n \n

\n - Check if is left child of its parent \n
- \n
- \n is left child of . Then contains sum of range of and another child which is outside the range and we don\'t need parent sum. Add to without its parent and set to point to the left of on the upper level. \n
- \n is not left child of . Then parent contains sum of range which lies in . Add to and set to point to the parent of \n \n

\n

\n - Check if is right child of its parent \n

**Java**

public int sumRange(int l, int r) {\n // get leaf with value \'l\'\n l += n;\n // get leaf with value \'r\'\n r += n;\n int sum = 0;\n while (l <= r) {\n if ((l % 2) == 1) {\n sum += tree[l];\n l++;\n }\n if ((r % 2) == 0) {\n sum += tree[r];\n r--;\n }\n l /= 2;\n r /= 2;\n }\n return sum;\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nTime complexity is because on each iteration of the algorithm we move one level up, either to the parent of the current node or to the next sibling of parent to the left or right direction till the two boundaries meet. In the worst-case scenario this happens at the root after iterations of the algorithm.

\n \n - \n
Space complexity : .

\n \n

The iterative version of Segment Trees was introduced in this article. A more intuitive, recursive version of Segment Trees to solve this problem is discussed here. The concept of Lazy Propagation is also introduced there.

\nThere is an alternative solution of the problem using Binary Indexed Tree. It is faster and simpler to code.\nYou can find it here.

\nAnalysis written by: @elmirap.

\n