# 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)

- Insert
- 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`

.

- First, update
- 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`

.

- Be clear that a

`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:`

1 | Input |

`Code:`

1 | /** |