## Approach 1: Fenwick Tree

• Time:Constructor: O(n\log n), update(index: int, val: int): O(\log n), sumRange(left: int, right: int): O(\log n)
• Space:O(n)

## C++

``````class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}

void update(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}

int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}

private:
vector<int> sums;

static inline int lowbit(int i) {
return i & -i;
}
};

class NumArray {
public:
NumArray(vector<int>& nums) : nums(nums), tree(nums.size()) {
for (int i = 0; i < nums.size(); ++i)
tree.update(i + 1, nums[i]);
}

void update(int index, int val) {
tree.update(index + 1, val - nums[index]);
nums[index] = val;
}

int sumRange(int left, int right) {
return tree.get(right + 1) - tree.get(left);
}

private:
vector<int> nums;
FenwickTree tree;
};
``````

## JAVA

``````class FenwickTree {
public FenwickTree(int n) {
sums = new int[n + 1];
}

public void update(int i, int delta) {
while (i < sums.length) {
sums[i] += delta;
i += lowbit(i);
}
}

public int get(int i) {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}

private int[] sums;

private static int lowbit(int i) {
return i & -i;
}
}

class NumArray {
public NumArray(int[] nums) {
this.nums = nums;
tree = new FenwickTree(nums.length);
for (int i = 0; i < nums.length; ++i)
tree.update(i + 1, nums[i]);
}

public void update(int index, int val) {
tree.update(index + 1, val - nums[index]);
nums[index] = val;
}

public int sumRange(int left, int right) {
return tree.get(right + 1) - tree.get(left);
}

private int[] nums;
private FenwickTree tree;
}
``````

## Python

``````class FenwickTree:
def __init__(self, n: int):
self.sums = [0] * (n + 1)

def update(self, i: int, delta: int) -> None:
while i < len(self.sums):
self.sums[i] += delta
i += self._lowbit(i)

def get(self, i: int) -> int:
sum = 0
while i > 0:
sum += self.sums[i]
i -= self._lowbit(i)
return sum

def _lowbit(self, i) -> int:
return i & -i

class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
self.tree = FenwickTree(len(nums))
for i, num in enumerate(nums):
self.tree.update(i + 1, num)

def update(self, index: int, val: int) -> None:
self.tree.update(index + 1, val - self.nums[index])
self.nums[index] = val

def sumRange(self, left: int, right: int) -> int:
return self.tree.get(right + 1) - self.tree.get(left)
``````