307. Range Sum Query - Mutable

Level - medium

Task

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]).

Объяснение

Задача требует от нас разработать структуру данных, которая поддерживает две операции:

update(index, val): Обновляет значение элемента в массиве по заданному индексу.
sumRange(left, right): Возвращает сумму элементов массива от индекса left до индекса right (включительно).

Основная сложность заключается в том, чтобы обеспечить эффективное выполнение обеих операций. Простая реализация с использованием массива может привести к высокой сложности для операции sumRange, особенно если массив большой.

Для решения этой задачи можно использовать различные структуры данных, такие как дерево отрезков (Segment Tree) или дерево Фенвика (Fenwick Tree / Binary Indexed Tree). Эти структуры позволяют выполнять обе операции за логарифмическое время, что является оптимальным решением.

Для решения задачи мы будем использовать дерево Фенвика (Fenwick Tree), также известное как Binary Indexed Tree. Эта структура данных позволяет эффективно выполнять операции обновления и вычисления суммы на отрезке.

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: