Problem Description

This problem asks you to implement a data structure that supports two operations on an integer array:

1. Update Operation: Change the value of an element at a specific index in the array
2. Range Sum Query: Calculate the sum of all elements between two given indices (inclusive)

You need to implement a NumArray class with three methods:

• NumArray(int[] nums): Constructor that initializes the data structure with the given integer array nums
• void update(int index, int val): Updates the element at position index to have the new value val
• int sumRange(int left, int right): Returns the sum of all elements from index left to index right (both inclusive)

For example, if you have an array [1, 3, 5]:

• sumRange(0, 2) would return 1 + 3 + 5 = 9
• After update(1, 2), the array becomes [1, 2, 5]
• Now sumRange(0, 2) would return 1 + 2 + 5 = 8

The challenge is to implement these operations efficiently, especially when there are many update and query operations. A naive approach would be to simply update the array directly and sum elements for each query, but this becomes inefficient with frequent operations.

The solution uses a Binary Indexed Tree (also known as Fenwick Tree) data structure, which allows both update and range sum query operations to be performed in O(log n) time complexity. This is much more efficient than the naive O(n) approach for range sum queries when dealing with multiple operations.

Intuition

When we need to frequently update array elements and calculate range sums, the naive approach has a trade-off problem:

• If we store the original array, updates are O(1) but range sum queries are O(n)
• If we store a prefix sum array, range sum queries are O(1) but updates become O(n) since we need to update all affected prefix sums

We need a data structure that balances both operations efficiently. This leads us to think about tree-based structures that can decompose the problem hierarchically.

The key insight is that we can represent partial sums in a clever way where:

1. Each position in our auxiliary array stores the sum of a specific range of elements
2. These ranges are determined by the binary representation of the index
3. Any prefix sum can be computed by combining a logarithmic number of these partial sums

The Binary Indexed Tree (Fenwick Tree) achieves this by using the least significant bit (LSB) of an index to determine the range of elements it's responsible for. The operation x & -x isolates the LSB, which tells us:

• How many elements this position covers
• Which position to jump to next when traversing the tree

For updates, we only need to update the nodes that include the changed element in their range. We find these nodes by repeatedly adding the LSB to the current position: x += x & -x.

For queries, we can compute a prefix sum by accumulating values while moving down the tree. We find the relevant nodes by repeatedly removing the LSB: x -= x & -x.

The beauty of this approach is that both operations traverse at most O(log n) nodes because we're essentially moving through the binary representation of the index, which has at most log n bits. This gives us the perfect balance: both updates and range queries in O(log n) time.

Solution Approach

The solution implements a Binary Indexed Tree (Fenwick Tree) to efficiently handle both update and range sum operations.

Binary Indexed Tree Implementation

The BinaryIndexedTree class maintains:

• n: the size of the array
• c: an auxiliary array of size n + 1 (1-indexed) that stores partial sums

Key Operations:

1. update(x, delta): Adds delta to the element at position x

   while x <= self.n:
       self.c[x] += delta
       x += x & -x

   • Starting from position x, we update all nodes that include this position in their range
   • x & -x gives us the least significant bit, which determines the jump distance
   • We keep jumping to parent nodes until we exceed the array size

2. query(x): Returns the prefix sum from index 1 to x

   s = 0
   while x > 0:
       s += self.c[x]
       x -= x & -x
   return s

   • We accumulate partial sums by traversing down the tree
   • x & -x tells us which position to jump to next
   • We continue until we reach 0

NumArray Implementation

The NumArray class wraps the Binary Indexed Tree to provide the required interface:

1. Constructor: Initializes the tree with the given array

   self.tree = BinaryIndexedTree(len(nums))
   for i, v in enumerate(nums, 1):
       self.tree.update(i, v)

   • Creates an empty tree
   • Inserts each element using 1-based indexing (Fenwick Trees are traditionally 1-indexed)

2. update(index, val): Updates the value at the given index

   prev = self.sumRange(index, index)
   self.tree.update(index + 1, val - prev)

   • First finds the current value at the index using sumRange
   • Updates the tree with the difference (val - prev) rather than the absolute value
   • Converts to 1-based indexing by adding 1 to the index

3. sumRange(left, right): Calculates the sum between indices

   return self.tree.query(right + 1) - self.tree.query(left)

   • Uses the prefix sum property: sum[left...right] = prefixSum[right] - prefixSum[left-1]
   • Adjusts for 1-based indexing by using right + 1 and left

Time Complexity

• Update: O(log n) - traverses at most log n nodes
• Range Sum Query: O(log n) - performs two prefix sum queries, each taking O(log n)
• Initialization: O(n log n) - performs n updates, each taking O(log n)

Space Complexity

• O(n) for storing the auxiliary array in the Binary Indexed Tree

Example Walkthrough

Let's walk through a small example with the array [1, 3, 5] to understand how the Binary Indexed Tree works.

Initial Setup:

• Original array: [1, 3, 5] (0-indexed)
• BIT array c: [0, 0, 0, 0] (1-indexed, size n+1)

Building the tree: We insert each element one by one.

1. Insert 1 at index 1:

   • update(1, 1): Start at position 1
   • c[1] += 1 → c = [0, 1, 0, 0]
   • Next position: 1 + (1 & -1) = 1 + 1 = 2
   • c[2] += 1 → c = [0, 1, 1, 0]
   • Next position: 2 + (2 & -2) = 2 + 2 = 4 (exceeds n=3, stop)

2. Insert 3 at index 2:

   • update(2, 3): Start at position 2
   • c[2] += 3 → c = [0, 1, 4, 0]
   • Next position: 2 + (2 & -2) = 2 + 2 = 4 (exceeds n=3, stop)

3. Insert 5 at index 3:

   • update(3, 5): Start at position 3
   • c[3] += 5 → c = [0, 1, 4, 5]
   • Next position: 3 + (3 & -3) = 3 + 1 = 4 (exceeds n=3, stop)

Final BIT array: c = [0, 1, 4, 5]

• c[1] stores sum of element at index 1: 1
• c[2] stores sum of elements at indices 1-2: 1 + 3 = 4
• c[3] stores sum of element at index 3: 5

Query Example: sumRange(0, 2) (sum all elements)

• Convert to 1-indexed: query(3) - query(0)
• query(3):
  • Start at position 3: s = 0 + c[3] = 0 + 5 = 5
  • Next position: 3 - (3 & -3) = 3 - 1 = 2
  • Add c[2]: s = 5 + 4 = 9
  • Next position: 2 - (2 & -2) = 2 - 2 = 0 (stop)
  • Result: 9
• query(0) = 0
• Final result: 9 - 0 = 9

Update Example: update(1, 2) (change index 1 from 3 to 2)

• Current value at index 1: sumRange(1, 1) = 3
• Delta: 2 - 3 = -1
• update(2, -1) in BIT (using 1-indexed position 2):
  • c[2] += -1 → c[2] = 4 - 1 = 3
  • Next position: 2 + 2 = 4 (exceeds n, stop)
• Updated BIT: c = [0, 1, 3, 5]

Query After Update: sumRange(0, 2)

• query(3) - query(0)
• query(3):
  • s = c[3] = 5
  • Next: s = 5 + c[2] = 5 + 3 = 8
  • Result: 8
• Final result: 8 - 0 = 8

The key insight is how the BIT uses binary representation to determine which nodes to update and query. Position 2 (binary: 10) is responsible for 2 elements because its LSB represents 2. Position 3 (binary: 11) is responsible for 1 element because its LSB represents 1. This clever indexing scheme ensures we only touch O(log n) nodes for any operation.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Initialization (__init__): O(n log n) where n is the length of the input array. The initialization creates a Binary Indexed Tree and performs n update operations. Each update operation takes O(log n) time as it traverses up the tree by adding the least significant bit (x += x & -x), which visits at most log n nodes.

• Update operation (update): O(log n). The update method first calls sumRange to get the previous value at the index, which takes O(log n) time. Then it calls the tree's update method with the difference, which also takes O(log n) time. Total: O(log n) + O(log n) = O(log n).

• Range sum query (sumRange): O(log n). The method performs two prefix sum queries using the Binary Indexed Tree's query method. Each query operation takes O(log n) time as it traverses down the tree by removing the least significant bit (x -= x & -x), visiting at most log n nodes. Total: O(log n) + O(log n) = O(log n).

Space Complexity:

O(n) where n is the length of the input array. The Binary Indexed Tree maintains an array c of size n + 1 to store the tree nodes. No additional significant space is used beyond this array. The __slots__ declaration helps optimize memory usage by preventing the creation of __dict__ for instances, but doesn't change the asymptotic space complexity.

Common Pitfalls

1. Index Confusion Between 0-based and 1-based Systems

The Pitfall: One of the most common mistakes when implementing a Binary Indexed Tree is mixing up 0-based indexing (used by the NumArray interface) and 1-based indexing (used internally by the Fenwick Tree). This can lead to:

• Off-by-one errors
• Incorrect range sum calculations
• Array index out of bounds exceptions
• Infinite loops in the update/query operations

Example of the mistake:

# WRONG: Forgetting to convert indices
def sumRange(self, left: int, right: int) -> int:
    return self.tree.query(right) - self.tree.query(left)  # Missing +1 adjustment

The Solution: Always be explicit about index conversions at the boundary between the public interface and the internal tree implementation:

def update(self, index: int, val: int) -> None:
    # Explicitly convert 0-based to 1-based
    tree_index = index + 1
    current_value = self.sumRange(index, index)
    self.tree.update(tree_index, val - current_value)

def sumRange(self, left: int, right: int) -> int:
    # Convert to 1-based: right+1 for inclusive, left stays as is for exclusive prefix
    return self.tree.query(right + 1) - self.tree.query(left)

2. Incorrect Delta Calculation in Update

The Pitfall: When updating a value, directly passing the new value instead of the difference (delta) to the tree's update method. The Binary Indexed Tree stores partial sums, so it needs the change amount, not the absolute value.

Example of the mistake:

# WRONG: Passing absolute value instead of delta
def update(self, index: int, val: int) -> None:
    self.tree.update(index + 1, val)  # This adds val to existing value!

The Solution: Calculate the difference between the new and old values:

def update(self, index: int, val: int) -> None:
    current_value = self.sumRange(index, index)
    delta = val - current_value
    self.tree.update(index + 1, delta)

3. Bit Manipulation Error in Tree Navigation

The Pitfall: Using incorrect bit manipulation for finding the next node to update or query. The expression x & -x isolates the least significant bit, which is crucial for tree traversal.

Example of the mistake:

# WRONG: Various incorrect bit manipulations
x += x & x      # Doesn't isolate LSB
x += x & (x-1)  # Removes LSB instead of isolating it
x += 1          # Simple increment doesn't follow tree structure

The Solution: Use the correct bit manipulation formulas:

def update(self, x: int, delta: int) -> None:
    while x <= self.n:
        self.c[x] += delta
        x += x & -x  # Correct: adds the least significant bit

def query(self, x: int) -> int:
    s = 0
    while x > 0:
        s += self.c[x]
        x -= x & -x  # Correct: removes the least significant bit
    return s

4. Initialization with Wrong Tree Size

The Pitfall: Creating the Binary Indexed Tree with size n instead of n + 1 for the internal array, or forgetting that the tree uses 1-based indexing.

Example of the mistake:

# WRONG: Array too small
def __init__(self, n: int) -> None:
    self.n = n
    self.c = [0] * n  # Should be n + 1

The Solution: Always allocate n + 1 elements for 1-based indexing:

def __init__(self, n: int) -> None:
    self.n = n
    self.c = [0] * (n + 1)  # Correct size for 1-based indexing