Facebook Pixel

327. Count of Range Sum

HardBinary Indexed TreeSegment TreeArrayBinary SearchDivide and ConquerOrdered SetMerge Sort
Leetcode Link

Problem Description

You are given an integer array nums and two integers lower and upper. Your task is to count how many range sums fall within the interval [lower, upper] (inclusive).

A range sum S(i, j) represents the sum of all elements in nums from index i to index j (inclusive), where i ≤ j.

For example, if nums = [1, 2, 3], the possible range sums are:

  • S(0, 0) = 1 (sum of elements from index 0 to 0)
  • S(0, 1) = 3 (sum of elements from index 0 to 1)
  • S(0, 2) = 6 (sum of elements from index 0 to 2)
  • S(1, 1) = 2 (sum of elements from index 1 to 1)
  • S(1, 2) = 5 (sum of elements from index 1 to 2)
  • S(2, 2) = 3 (sum of elements from index 2 to 2)

You need to count how many of these range sums have values between lower and upper (inclusive).

The solution uses a Binary Indexed Tree (Fenwick Tree) with coordinate compression to efficiently count valid range sums. It first computes prefix sums, then for each prefix sum, it counts how many previous prefix sums would create a valid range sum when subtracted from the current one. The key insight is that for a range sum S(i, j) to be valid, we need lower ≤ prefix[j+1] - prefix[i] ≤ upper, which can be rearranged to find valid values of prefix[i] given prefix[j+1].

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The naive approach would be to check every possible range sum S(i, j) by iterating through all pairs of indices, but this would take O(n²) time just to generate the sums, making it inefficient for large arrays.

The key insight is to transform the problem using prefix sums. If we compute the prefix sum array where prefix[i] represents the sum of elements from index 0 to i-1, then any range sum S(i, j) can be expressed as prefix[j+1] - prefix[i].

Now the problem becomes: for each ending position j, count how many starting positions i (where i ≤ j) satisfy: lower ≤ prefix[j+1] - prefix[i] ≤ upper

Rearranging this inequality: prefix[j+1] - upper ≤ prefix[i] ≤ prefix[j+1] - lower

This means for each prefix sum prefix[j+1], we need to count how many previous prefix sums fall within the range [prefix[j+1] - upper, prefix[j+1] - lower].

This is a classic "count elements in range" problem that can be solved efficiently using a data structure like Binary Indexed Tree (BIT). As we process each prefix sum:

  1. Query the BIT to count how many previously seen prefix sums fall in our target range
  2. Add the current prefix sum to the BIT for future queries

To handle arbitrary values efficiently, we use coordinate compression - mapping all relevant values (prefix sums and their boundaries) to a smaller range of indices that can be used with the BIT. This allows us to work with the relative ordering of values rather than their absolute magnitudes.

The time complexity becomes O(n log n) due to sorting for coordinate compression and BIT operations, which is much better than the naive O(n²) approach.

Solution Approach

The solution implements a Binary Indexed Tree (Fenwick Tree) with coordinate compression to efficiently count range sums within the given bounds.

Step 1: Build Prefix Sum Array

s = list(accumulate(nums, initial=0))

We create a prefix sum array where s[i] represents the sum of elements from index 0 to i-1. The initial=0 parameter ensures s[0] = 0, representing an empty prefix.

Step 2: Coordinate Compression

arr = sorted(set(v for x in s for v in (x, x - lower, x - upper)))

For each prefix sum x, we need to query ranges [x - upper, x - lower]. We collect all unique values that will be used (the prefix sums themselves and their range boundaries) and sort them. This creates a mapping from actual values to compressed indices (0 to len(arr)-1).

Step 3: Initialize Binary Indexed Tree

tree = BinaryIndexedTree(len(arr))

The BIT is initialized with size equal to the number of unique values. It supports:

  • update(x, v): Add value v at position x
  • query(x): Get sum of values from position 1 to x

Step 4: Process Each Prefix Sum

for x in s:
    l = bisect_left(arr, x - upper) + 1
    r = bisect_left(arr, x - lower) + 1
    ans += tree.query(r) - tree.query(l - 1)
    tree.update(bisect_left(arr, x) + 1, 1)

For each prefix sum x:

  1. Find the compressed indices for the range [x - upper, x - lower]:

    • l is the 1-indexed position of x - upper in the compressed array
    • r is the 1-indexed position of x - lower in the compressed array

  2. Query the BIT to count how many previous prefix sums fall in this range:

    • tree.query(r) gives count of all values ≤ x - lower
    • tree.query(l - 1) gives count of all values < x - upper
    • The difference gives count in range [x - upper, x - lower]

  3. Add the current prefix sum to the BIT:

    • Find its compressed index using bisect_left(arr, x) + 1
    • Update the BIT to record this prefix sum for future queries

Binary Indexed Tree Implementation

  • update(x, v): Adds v to position x and propagates updates using x += x & -x (adds the least significant bit)
  • query(x): Sums values from 1 to x by traversing using x -= x & -x (removes the least significant bit)

The algorithm processes each prefix sum once with O(log n) BIT operations, resulting in overall O(n log n) time complexity.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a concrete example:

  • nums = [-2, 5, -1]
  • lower = -2
  • upper = 2

Step 1: Build Prefix Sum Array

s = [0, -2, 3, 2]
  • s[0] = 0 (empty prefix)
  • s[1] = 0 + (-2) = -2
  • s[2] = -2 + 5 = 3
  • s[3] = 3 + (-1) = 2

Step 2: Coordinate Compression For each prefix sum x in s, we need values: x, x - lower, and x - upper:

  • For x = 0: values are 0, 0 - (-2) = 2, 0 - 2 = -2
  • For x = -2: values are -2, -2 - (-2) = 0, -2 - 2 = -4
  • For x = 3: values are 3, 3 - (-2) = 5, 3 - 2 = 1
  • For x = 2: values are 2, 2 - (-2) = 4, 2 - 2 = 0

Sorted unique values: arr = [-4, -2, 0, 1, 2, 3, 4, 5]

Step 3: Initialize BIT Create a BIT of size 8 (all initially 0).

Step 4: Process Each Prefix Sum

Processing s[0] = 0:

  • Range to query: [0 - 2, 0 - (-2)] = [-2, 2]
  • Compressed indices: l = 2, r = 5 (1-indexed)
  • Query BIT: tree.query(5) - tree.query(1) = 0 - 0 = 0
  • No previous prefix sums exist, so count = 0
  • Update BIT at position 3 (compressed index of 0)
  • BIT state: position 3 has value 1

Processing s[1] = -2:

  • Range to query: [-2 - 2, -2 - (-2)] = [-4, 0]
  • Compressed indices: l = 1, r = 3
  • Query BIT: tree.query(3) - tree.query(0) = 1 - 0 = 1
  • Found 1 valid range: S(0,0) = -2 - 0 = -2 ✓ (within [-2, 2])
  • Update BIT at position 2 (compressed index of -2)
  • Running count: 1

Processing s[2] = 3:

  • Range to query: [3 - 2, 3 - (-2)] = [1, 5]
  • Compressed indices: l = 4, r = 8
  • Query BIT: tree.query(8) - tree.query(3) = 0 - 1 = 0
  • No valid ranges ending at index 1
  • Update BIT at position 6 (compressed index of 3)
  • Running count: 1

Processing s[3] = 2:

  • Range to query: [2 - 2, 2 - (-2)] = [0, 4]
  • Compressed indices: l = 3, r = 7
  • Query BIT: tree.query(7) - tree.query(2) = 2 - 1 = 1
  • Found 1 valid range: S(1,2) = 2 - (-2) = 4... wait, 4 > 2, not valid
  • Actually checking: we need 2 - prefix[i] in [-2, 2]
    • prefix[0] = 0: gives 2 - 0 = 2 ✓
  • Running count: 2

Wait, let me recalculate more carefully:

Processing s[3] = 2:

  • We need previous prefix sums p such that 2 - p is in [-2, 2]
  • This means -2 ≤ 2 - p ≤ 2
  • Rearranging: 0 ≤ p ≤ 4
  • Previous prefix sums: 0, -2, 3
  • Check which satisfy 0 ≤ p ≤ 4: 0 ✓, 3 ✓
  • So we find 2 valid ranges:
    • S(0,2) = 2 - 0 = 2 ✓
    • S(2,2) = 2 - 3 = -1 ✓

Final Answer: 3 The valid range sums are:

  1. S(0,0) = -2
  2. S(0,2) = 2
  3. S(2,2) = -1

Solution Implementation

1from typing import List
2from itertools import accumulate
3from bisect import bisect_left
4
5
6class BinaryIndexedTree:
7    """
8    Binary Indexed Tree (Fenwick Tree) for efficient range sum queries and updates.
9    Uses 1-based indexing internally.
10    """
11  
12    def __init__(self, n: int) -> None:
13        """
14        Initialize a Binary Indexed Tree with size n.
15      
16        Args:
17            n: The size of the tree
18        """
19        self.size = n
20        self.tree = [0] * (n + 1)  # 1-indexed array
21  
22    def update(self, index: int, delta: int) -> None:
23        """
24        Add delta to the element at the given index.
25      
26        Args:
27            index: The position to update (1-based)
28            delta: The value to add
29        """
30        while index <= self.size:
31            self.tree[index] += delta
32            # Move to next index by adding the least significant bit
33            index += index & (-index)
34  
35    def query(self, index: int) -> int:
36        """
37        Get the prefix sum from index 1 to the given index.
38      
39        Args:
40            index: The ending position for the prefix sum (1-based)
41          
42        Returns:
43            The sum of elements from 1 to index
44        """
45        result = 0
46        while index > 0:
47            result += self.tree[index]
48            # Move to parent by removing the least significant bit
49            index -= index & (-index)
50        return result
51
52
53class Solution:
54    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
55        """
56        Count the number of range sums that lie in [lower, upper].
57        A range sum S(i, j) is defined as the sum of elements from index i to j (inclusive).
58      
59        Args:
60            nums: The input array
61            lower: The lower bound of the range
62            upper: The upper bound of the range
63          
64        Returns:
65            The count of valid range sums
66        """
67        # Calculate prefix sums (including initial 0 for empty prefix)
68        prefix_sums = list(accumulate(nums, initial=0))
69      
70        # Create a sorted array of all unique values we need to track
71        # For each prefix sum x, we need x itself, x-lower, and x-upper
72        unique_values = set()
73        for prefix_sum in prefix_sums:
74            unique_values.add(prefix_sum)
75            unique_values.add(prefix_sum - lower)
76            unique_values.add(prefix_sum - upper)
77      
78        # Sort unique values for coordinate compression
79        sorted_values = sorted(unique_values)
80      
81        # Initialize Binary Indexed Tree with compressed coordinate space
82        fenwick_tree = BinaryIndexedTree(len(sorted_values))
83      
84        count = 0
85      
86        # Process each prefix sum
87        for current_sum in prefix_sums:
88            # Find the range of valid previous prefix sums
89            # We need previous_sum such that: lower <= current_sum - previous_sum <= upper
90            # Which means: current_sum - upper <= previous_sum <= current_sum - lower
91          
92            # Get compressed coordinates (1-based for BIT)
93            left_bound = bisect_left(sorted_values, current_sum - upper) + 1
94            right_bound = bisect_left(sorted_values, current_sum - lower) + 1
95          
96            # Count how many previous prefix sums fall in this range
97            count += fenwick_tree.query(right_bound) - fenwick_tree.query(left_bound - 1)
98          
99            # Add current prefix sum to the tree for future queries
100            current_position = bisect_left(sorted_values, current_sum) + 1
101            fenwick_tree.update(current_position, 1)
102      
103        return count
104
1import java.util.Arrays;
2
3/**
4 * Binary Indexed Tree (Fenwick Tree) for efficient range sum queries and updates
5 */
6class BinaryIndexedTree {
7    private int size;
8    private int[] tree;
9
10    /**
11     * Initialize the Binary Indexed Tree with given size
12     * @param size the size of the tree (1-indexed)
13     */
14    public BinaryIndexedTree(int size) {
15        this.size = size;
16        this.tree = new int[size + 1];
17    }
18
19    /**
20     * Update the value at index by adding delta
21     * @param index the 1-based index to update
22     * @param delta the value to add
23     */
24    public void update(int index, int delta) {
25        while (index <= size) {
26            tree[index] += delta;
27            // Move to next index by adding the least significant bit
28            index += index & -index;
29        }
30    }
31
32    /**
33     * Query the prefix sum from index 1 to index
34     * @param index the 1-based index to query up to
35     * @return the prefix sum
36     */
37    public int query(int index) {
38        int sum = 0;
39        while (index > 0) {
40            sum += tree[index];
41            // Move to parent index by removing the least significant bit
42            index -= index & -index;
43        }
44        return sum;
45    }
46}
47
48/**
49 * Solution for counting range sums within a given range [lower, upper]
50 */
51class Solution {
52    /**
53     * Count the number of range sums that lie in [lower, upper]
54     * @param nums the input array
55     * @param lower the lower bound of the range
56     * @param upper the upper bound of the range
57     * @return the count of valid range sums
58     */
59    public int countRangeSum(int[] nums, int lower, int upper) {
60        int n = nums.length;
61      
62        // Calculate prefix sums
63        long[] prefixSums = new long[n + 1];
64        for (int i = 0; i < n; i++) {
65            prefixSums[i + 1] = prefixSums[i] + nums[i];
66        }
67      
68        // Create array with all possible values we need to track:
69        // prefixSum[i], prefixSum[i] - lower, prefixSum[i] - upper
70        long[] allValues = new long[n * 3 + 3];
71        for (int i = 0, j = 0; i <= n; i++, j += 3) {
72            allValues[j] = prefixSums[i];
73            allValues[j + 1] = prefixSums[i] - lower;
74            allValues[j + 2] = prefixSums[i] - upper;
75        }
76      
77        // Sort and remove duplicates for coordinate compression
78        Arrays.sort(allValues);
79        int uniqueCount = 0;
80        for (int i = 0; i < allValues.length; i++) {
81            if (i == 0 || allValues[i] != allValues[i - 1]) {
82                allValues[uniqueCount++] = allValues[i];
83            }
84        }
85      
86        // Use Binary Indexed Tree to count valid range sums
87        BinaryIndexedTree fenwickTree = new BinaryIndexedTree(uniqueCount);
88        int result = 0;
89      
90        for (long currentSum : prefixSums) {
91            // Find indices for range [currentSum - upper, currentSum - lower]
92            int leftIndex = binarySearch(allValues, uniqueCount, currentSum - upper);
93            int rightIndex = binarySearch(allValues, uniqueCount, currentSum - lower);
94          
95            // Count how many prefix sums fall in the valid range
96            result += fenwickTree.query(rightIndex) - fenwickTree.query(leftIndex - 1);
97          
98            // Add current prefix sum to the tree
99            fenwickTree.update(binarySearch(allValues, uniqueCount, currentSum), 1);
100        }
101      
102        return result;
103    }
104
105    /**
106     * Binary search to find the 1-based index of target in sorted array
107     * @param nums the sorted array
108     * @param length the effective length of the array
109     * @param target the target value to search for
110     * @return the 1-based index of the target (or where it would be inserted)
111     */
112    private int binarySearch(long[] nums, int length, long target) {
113        int left = 0;
114        int right = length;
115      
116        while (left < right) {
117            int mid = (left + right) >> 1;
118            if (nums[mid] >= target) {
119                right = mid;
120            } else {
121                left = mid + 1;
122            }
123        }
124      
125        // Return 1-based index for Binary Indexed Tree
126        return left + 1;
127    }
128}
129
1class BinaryIndexedTree {
2public:
3    // Constructor: Initialize BIT with size n
4    BinaryIndexedTree(int n) : size(n), tree(n + 1, 0) {}
5
6    // Update: Add value to position index (1-indexed)
7    void update(int index, int value) {
8        while (index <= size) {
9            tree[index] += value;
10            index += index & (-index);  // Move to next node using lowbit
11        }
12    }
13
14    // Query: Get prefix sum from 1 to index (1-indexed)
15    int query(int index) {
16        int sum = 0;
17        while (index > 0) {
18            sum += tree[index];
19            index -= index & (-index);  // Move to parent node using lowbit
20        }
21        return sum;
22    }
23
24private:
25    int size;
26    vector<int> tree;
27};
28
29class Solution {
30public:
31    int countRangeSum(vector<int>& nums, int lower, int upper) {
32        using ll = long long;
33        int n = nums.size();
34      
35        // Build prefix sum array
36        vector<ll> prefixSum(n + 1, 0);
37        for (int i = 0; i < n; ++i) {
38            prefixSum[i + 1] = prefixSum[i] + nums[i];
39        }
40      
41        // Collect all values needed for coordinate compression
42        // For each prefix sum s[i], we need:
43        // - s[i] itself
44        // - s[i] - lower (upper bound for valid range)
45        // - s[i] - upper (lower bound for valid range)
46        vector<ll> allValues;
47        allValues.reserve((n + 1) * 3);
48        for (int i = 0; i <= n; ++i) {
49            allValues.push_back(prefixSum[i]);
50            allValues.push_back(prefixSum[i] - lower);
51            allValues.push_back(prefixSum[i] - upper);
52        }
53      
54        // Coordinate compression: sort and remove duplicates
55        sort(allValues.begin(), allValues.end());
56        allValues.erase(unique(allValues.begin(), allValues.end()), allValues.end());
57        int compressedSize = allValues.size();
58      
59        // Initialize Binary Indexed Tree with compressed size
60        BinaryIndexedTree fenwickTree(compressedSize);
61      
62        int result = 0;
63      
64        // Process each prefix sum
65        for (int i = 0; i <= n; ++i) {
66            // Find range [s[i] - upper, s[i] - lower] in compressed coordinates
67            // We're looking for all j < i where s[i] - s[j] is in [lower, upper]
68            // Equivalently, s[j] is in [s[i] - upper, s[i] - lower]
69          
70            // Get compressed indices (1-indexed for BIT)
71            int leftBound = lower_bound(allValues.begin(), allValues.end(), 
72                                       prefixSum[i] - upper) - allValues.begin() + 1;
73            int rightBound = lower_bound(allValues.begin(), allValues.end(), 
74                                        prefixSum[i] - lower) - allValues.begin() + 1;
75          
76            // Count valid prefix sums in range using BIT range query
77            result += fenwickTree.query(rightBound) - fenwickTree.query(leftBound - 1);
78          
79            // Add current prefix sum to BIT for future queries
80            int currentIndex = lower_bound(allValues.begin(), allValues.end(), 
81                                          prefixSum[i]) - allValues.begin() + 1;
82            fenwickTree.update(currentIndex, 1);
83        }
84      
85        return result;
86    }
87};
88
1// Binary Indexed Tree (Fenwick Tree) for efficient range sum queries
2let n: number;
3let tree: number[];
4
5// Initialize the Binary Indexed Tree with size n
6function initBIT(size: number): void {
7    n = size;
8    tree = Array(n + 1).fill(0);
9}
10
11// Update the BIT by adding value at position index
12function update(index: number, value: number): void {
13    while (index <= n) {
14        tree[index] += value;
15        // Move to next index by adding the rightmost set bit
16        index += index & -index;
17    }
18}
19
20// Query the prefix sum from index 1 to index
21function query(index: number): number {
22    let sum = 0;
23    while (index > 0) {
24        sum += tree[index];
25        // Move to parent by removing the rightmost set bit
26        index -= index & -index;
27    }
28    return sum;
29}
30
31// Binary search to find the leftmost position where nums[pos] >= target
32// Returns 1-indexed position for BIT compatibility
33function binarySearch(nums: number[], length: number, target: number): number {
34    let left = 0;
35    let right = length;
36  
37    while (left < right) {
38        const mid = (left + right) >> 1;
39        if (nums[mid] >= target) {
40            right = mid;
41        } else {
42            left = mid + 1;
43        }
44    }
45  
46    // Return 1-indexed position for BIT
47    return left + 1;
48}
49
50// Count the number of range sums that lie in [lower, upper]
51function countRangeSum(nums: number[], lower: number, upper: number): number {
52    const length = nums.length;
53  
54    // Calculate prefix sums
55    const prefixSums = Array(length + 1).fill(0);
56    for (let i = 0; i < length; i++) {
57        prefixSums[i + 1] = prefixSums[i] + nums[i];
58    }
59  
60    // Create array with all possible values we need to track:
61    // prefixSum[i], prefixSum[i] - lower, prefixSum[i] - upper
62    let allValues: number[] = Array((length + 1) * 3);
63    for (let i = 0, j = 0; i <= length; i++, j += 3) {
64        allValues[j] = prefixSums[i];
65        allValues[j + 1] = prefixSums[i] - lower;
66        allValues[j + 2] = prefixSums[i] - upper;
67    }
68  
69    // Sort and remove duplicates for coordinate compression
70    allValues.sort((a, b) => a - b);
71    let uniqueCount = 0;
72    for (let i = 0; i < allValues.length; i++) {
73        if (i === 0 || allValues[i] !== allValues[i - 1]) {
74            allValues[uniqueCount++] = allValues[i];
75        }
76    }
77    allValues = allValues.slice(0, uniqueCount);
78  
79    // Initialize BIT with compressed coordinate size
80    initBIT(uniqueCount);
81  
82    let result = 0;
83  
84    // For each prefix sum, count valid range sums ending at current position
85    for (const currentSum of prefixSums) {
86        // Find range of valid previous prefix sums
87        // We need: lower <= currentSum - prevSum <= upper
88        // Which means: currentSum - upper <= prevSum <= currentSum - lower
89        const leftBound = binarySearch(allValues, uniqueCount, currentSum - upper);
90        const rightBound = binarySearch(allValues, uniqueCount, currentSum - lower);
91      
92        // Count how many valid previous sums exist
93        result += query(rightBound) - query(leftBound - 1);
94      
95        // Add current sum to the BIT for future queries
96        update(binarySearch(allValues, uniqueCount, currentSum), 1);
97    }
98  
99    return result;
100}
101

Time and Space Complexity

Time Complexity: O(n log n)

The algorithm consists of several main steps:

  1. Computing prefix sums using accumulate: O(n)
  2. Creating and sorting the coordinate compression array arr:
    • Creating the set of values (at most 3n elements): O(n)
    • Sorting: O(n log n)
  3. Main loop iterating through prefix sums:
    • For each of n+1 prefix sums:
      • Two binary searches using bisect_left: O(log n) each
      • Two BIT query operations: O(log n) each
      • One BIT update operation: O(log n)
    • Total for loop: O(n log n)

Overall time complexity: O(n) + O(n log n) + O(n log n) = O(n log n)

Space Complexity: O(n)

The space usage includes:

  1. Prefix sum array s: O(n)
  2. Coordinate compression array arr: O(n) (at most 3n unique elements)
  3. Binary Indexed Tree array c: O(n) (size proportional to compressed coordinates)
  4. Temporary set for deduplication: O(n)

Overall space complexity: O(n)

Common Pitfalls

1. Incorrect Range Boundary Calculation

One of the most common mistakes is incorrectly calculating which previous prefix sums create valid range sums. Developers often confuse the inequality direction or bounds.

Pitfall Example:

# WRONG: Reversed inequality
left_bound = bisect_left(sorted_values, current_sum - lower) + 1  # Wrong!
right_bound = bisect_left(sorted_values, current_sum - upper) + 1  # Wrong!

Why it's wrong: For a range sum S(i, j) = prefix[j+1] - prefix[i] to be valid, we need:

  • lower ≤ prefix[j+1] - prefix[i] ≤ upper
  • Rearranging: prefix[j+1] - upper ≤ prefix[i] ≤ prefix[j+1] - lower

So when looking for valid previous prefix sums given current prefix sum x, we need the range [x - upper, x - lower], not [x - lower, x - upper].

Correct Solution:

left_bound = bisect_left(sorted_values, current_sum - upper) + 1
right_bound = bisect_left(sorted_values, current_sum - lower) + 1

2. Forgetting to Include Values in Coordinate Compression

Another pitfall is not including all necessary values in the coordinate compression step, leading to incorrect index lookups.

Pitfall Example:

# WRONG: Only compressing the prefix sums themselves
unique_values = set(prefix_sums)  # Missing boundary values!

Why it's wrong: We need to query ranges [x - upper, x - lower] for each prefix sum x. If these boundary values aren't in our compressed coordinate system, we can't properly find their positions.

Correct Solution:

unique_values = set()
for prefix_sum in prefix_sums:
    unique_values.add(prefix_sum)
    unique_values.add(prefix_sum - lower)
    unique_values.add(prefix_sum - upper)

3. Off-by-One Errors with BIT Indexing

Binary Indexed Trees use 1-based indexing, while Python uses 0-based indexing. Mixing these can cause subtle bugs.

Pitfall Example:

# WRONG: Using 0-based index directly with BIT
position = bisect_left(sorted_values, current_sum)  # 0-based
fenwick_tree.update(position, 1)  # BIT expects 1-based!

Correct Solution:

position = bisect_left(sorted_values, current_sum) + 1  # Convert to 1-based
fenwick_tree.update(position, 1)

4. Processing Order: Query Before Update

The order of operations is crucial. We must query for valid previous prefix sums before adding the current one to avoid counting invalid ranges.

Pitfall Example:

# WRONG: Updating before querying
for current_sum in prefix_sums:
    fenwick_tree.update(bisect_left(sorted_values, current_sum) + 1, 1)  # Wrong order!
    count += fenwick_tree.query(right_bound) - fenwick_tree.query(left_bound - 1)

Why it's wrong: If we update first, we might count range sums where i > j, which are invalid by definition.

Correct Solution:

for current_sum in prefix_sums:
    # Query first to find valid ranges with previous prefix sums
    count += fenwick_tree.query(right_bound) - fenwick_tree.query(left_bound - 1)
    # Then update with current prefix sum
    fenwick_tree.update(bisect_left(sorted_values, current_sum) + 1, 1)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Divide and Conquer Intro

https assets algo monster cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger problem using the solutions

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More