# Leetcode 307 - Range sum query - mutable (🌳 Binary Indexed Tree)

Note:

• Just use preSum will have O(n) on updating, we need something faster.
• • Create a tree array with size 2 * nums_length.
• Insert nums[i] into the end of tree[].
• Baed on tree[i] = tree[2*i] + tree[2*i + 1], fill the preceding cells too. (Some cells might be left empty)
• Now even it’s still an array, but it is equivalent to something like
• • How to update a num?
• First, update tree[len + index].
• Then based on pos = len + index, update tree[pos / 2] = tree[left] + tree[right].
• Be careful that based on whether pos is even or odd, there are some adjustments for left and right.
• If pos is even, left = pos, right = pos + 1.
• If pos is odd, left = pos - 1, right = pos.
• Then update pos as pos / 2, and do this till pos === 0.
• How to calculate sum?
• Be clear that a sum treeNode can only work when left is even and right is odd.
• Add offset numsLen to left and right first.
• If left is odd, we need to add tree[left] to sum, and do left++.
• If right is even, we need to add tree[right] to sum, and do right--.
• Next, we need to find the parentNode of leftNode and rightNode.
• So, do left >> 1 and right >> 1.
• When we’ve found the parent node, it will be added to sum.
• Return sum.

Question:

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 indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• void update(int index, int val) Updates the value of nums[index] to be val.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example:

Code: