← Back to DevBytes
JavaScript August 07, 2026 15 min read

Solving Range Sum Query in JavaScript: Step-by-Step Guide

Introduction to Range Sum Query

The Range Sum Query (RSQ) is one of the most fundamental problems in computer science and competitive programming. Given an array of numbers, you need to answer multiple queries that ask for the sum of elements between two indices, typically denoted as sum(arr, L, R). While the problem sounds simple, the challenge lies in answering these queries efficiently, especially when the array is large and there are many queries — or when the array can be updated between queries.

In this tutorial, we'll explore several approaches to solving the Range Sum Query problem in JavaScript, starting from the naive solution and progressively building toward more sophisticated data structures like prefix sums, Fenwick trees (Binary Indexed Trees), and segment trees. By the end, you'll understand the trade-offs between each approach and know exactly when to use which.

Why Range Sum Query Matters

Range Sum Query is not just an academic exercise. It appears in countless real-world scenarios:

The key insight is that a naive approach — looping through the array for every query — becomes prohibitively slow when you have millions of elements and thousands of queries. Understanding efficient RSQ solutions teaches you core algorithmic concepts like prefix computation, binary indexing, and tree-based data structures that transfer to many other problems.

Problem Definition

Formally, the Range Sum Query problem is defined as follows:

There are two common variants of this problem:

We'll address both variants in this tutorial.

Approach 1: The Naive Solution

The most straightforward approach is to loop through the array from index L to R for each query and accumulate the sum. Let's implement this first to establish a baseline.

class RangeSumNaive {
  constructor(arr) {
    this.arr = [...arr]; // store a copy of the array
  }

  sumRange(L, R) {
    let total = 0;
    for (let i = L; i <= R; i++) {
      total += this.arr[i];
    }
    return total;
  }
}

// Usage example
const rsq = new RangeSumNaive([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(rsq.sumRange(0, 3)); // 3 + 1 + 4 + 1 = 9
console.log(rsq.sumRange(2, 5)); // 4 + 1 + 5 + 9 = 19
console.log(rsq.sumRange(4, 7)); // 5 + 9 + 2 + 6 = 22

This approach works, but its time complexity is O(n) per query. If you have q queries, the total time becomes O(n * q), which is unacceptable for large inputs. For example, with n = 100,000 and q = 100,000, this could mean 10 billion operations.

Approach 2: Prefix Sum Array (Immutable Array)

If the array is immutable (never changes), we can precompute a prefix sum array that allows us to answer each query in O(1) time. The idea is simple: create an array where each element at index i stores the sum of all elements from index 0 to i in the original array.

Once we have the prefix sum array, the sum of any range [L, R] can be computed as prefix[R] - prefix[L-1]. For the edge case where L = 0, the answer is simply prefix[R].

class RangeSumPrefix {
  constructor(arr) {
    this.prefix = new Array(arr.length);
    this.prefix[0] = arr[0];
    for (let i = 1; i < arr.length; i++) {
      this.prefix[i] = this.prefix[i - 1] + arr[i];
    }
  }

  sumRange(L, R) {
    if (L === 0) return this.prefix[R];
    return this.prefix[R] - this.prefix[L - 1];
  }
}

// Usage example
const rsq = new RangeSumPrefix([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(rsq.sumRange(0, 3)); // 9
console.log(rsq.sumRange(2, 5)); // 19
console.log(rsq.sumRange(4, 7)); // 22

The construction of the prefix array takes O(n) time, and each query is answered in O(1) time. The total time for q queries is O(n + q), which is a massive improvement over the naive approach.

Using a Sentinel Value for Cleaner Code

To avoid the L === 0 edge case, we can use a prefix array that is one element longer, with prefix[0] = 0. This way, prefix[i] always represents the sum of elements from index 0 to i - 1 in the original array, and the range sum formula becomes uniformly prefix[R + 1] - prefix[L].

class RangeSumPrefixClean {
  constructor(arr) {
    // prefix[i] = sum of arr[0..i-1], prefix[0] = 0
    this.prefix = new Array(arr.length + 1);
    this.prefix[0] = 0;
    for (let i = 0; i < arr.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + arr[i];
    }
  }

  sumRange(L, R) {
    return this.prefix[R + 1] - this.prefix[L];
  }
}

const rsq = new RangeSumPrefixClean([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(rsq.sumRange(0, 3)); // 9
console.log(rsq.sumRange(2, 5)); // 19
console.log(rsq.sumRange(4, 7)); // 22

This version is cleaner and less error-prone, which is especially valuable in competitive programming or interview settings where off-by-one errors can be costly.

Approach 3: Fenwick Tree / Binary Indexed Tree (Mutable Array)

The prefix sum approach breaks down when the array needs to be updated. If you change a single element, you'd need to recompute the entire prefix array, which takes O(n) time per update. The Fenwick Tree (also known as a Binary Indexed Tree or BIT) solves this problem by supporting both point updates and range sum queries in O(log n) time.

The Fenwick Tree is based on a clever observation about binary representation. Each index i in the tree is responsible for a range of elements whose length is determined by the lowest set bit in i. The key operations use the trick of isolating the lowest set bit using i & (-i), which works because of two's complement arithmetic.

class FenwickTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(this.n + 1).fill(0);
    // Build the tree in O(n)
    for (let i = 0; i < this.n; i++) {
      this.tree[i + 1] = arr[i];
    }
    for (let i = 1; i <= this.n; i++) {
      const parent = i + (i & (-i));
      if (parent <= this.n) {
        this.tree[parent] += this.tree[i];
      }
    }
  }

  // Add 'delta' to the element at index 'i' (0-based)
  update(i, delta) {
    i++; // convert to 1-based index
    while (i <= this.n) {
      this.tree[i] += delta;
      i += i & (-i); // move to the next responsible node
    }
  }

  // Returns the prefix sum from index 0 to i (inclusive, 0-based)
  prefixSum(i) {
    i++; // convert to 1-based index
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= i & (-i); // move to the parent node
    }
    return sum;
  }

  // Returns the sum of elements from index L to R (inclusive, 0-based)
  sumRange(L, R) {
    if (L === 0) return this.prefixSum(R);
    return this.prefixSum(R) - this.prefixSum(L - 1);
  }
}

// Usage example
const ft = new FenwickTree([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(ft.sumRange(0, 3)); // 9
console.log(ft.sumRange(2, 5)); // 19

// Update: change arr[2] from 4 to 10 (delta = +6)
ft.update(2, 6);
console.log(ft.sumRange(0, 3)); // 9 + 6 = 15
console.log(ft.sumRange(2, 5)); // 19 + 6 = 25

The Fenwick Tree is remarkably compact — it uses only O(n) space (a single array) and both update and sumRange operations run in O(log n) time. This makes it the go-to choice for mutable range sum problems.

How the Fenwick Tree Works Internally

Each node at index i in the tree stores the sum of a range of elements. The length of this range is i & (-i), which is the value of the lowest set bit in i. For example:

When you call prefixSum(i), you start at index i and repeatedly strip off the lowest set bit, accumulating the values at each node you visit. This traces a path through the tree that covers exactly the range [1, i] without overlap. The update operation does the reverse — it propagates the change to all nodes that cover the updated index.

Approach 4: Segment Tree (Mutable Array)

The Segment Tree is another powerful data structure for range queries. While the Fenwick Tree is more space-efficient and simpler to implement for sum queries, the Segment Tree is more general — it can handle range minimum queries, range maximum queries, range GCD, and even range updates with lazy propagation. If you need to support multiple types of range queries, the Segment Tree is the better choice.

A Segment Tree is a binary tree where each leaf node represents a single element of the array, and each internal node represents the sum (or other associative operation) of its children. The tree is typically stored in an array of size 2 * 2^ceil(log2(n)), which is at most 4n.

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    // Allocate enough space for the tree (at most 4 * n)
    this.tree = new Array(4 * this.n);
    this.build(arr, 0, 0, this.n - 1);
  }

  // Recursively build the tree
  // node: current node index in the tree array
  // start, end: range of the original array this node covers
  build(arr, node, start, end) {
    if (start === end) {
      // Leaf node
      this.tree[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      const leftChild = 2 * node + 1;
      const rightChild = 2 * node + 2;
      this.build(arr, leftChild, start, mid);
      this.build(arr, rightChild, mid + 1, end);
      this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
    }
  }

  // Update the element at 'index' to 'value'
  update(index, value, node = 0, start = 0, end = this.n - 1) {
    if (start === end) {
      this.tree[node] = value;
    } else {
      const mid = Math.floor((start + end) / 2);
      const leftChild = 2 * node + 1;
      const rightChild = 2 * node + 2;
      if (index <= mid) {
        this.update(index, value, leftChild, start, mid);
      } else {
        this.update(index, value, rightChild, mid + 1, end);
      }
      this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
    }
  }

  // Query the sum of elements from L to R (inclusive)
  sumRange(L, R, node = 0, start = 0, end = this.n - 1) {
    // Range represented by this node is completely outside the query range
    if (R < start || end < L) {
      return 0;
    }
    // Range represented by this node is completely inside the query range
    if (L <= start && end <= R) {
      return this.tree[node];
    }
    // Partial overlap — query both children
    const mid = Math.floor((start + end) / 2);
    const leftChild = 2 * node + 1;
    const rightChild = 2 * node + 2;
    const leftSum = this.sumRange(L, R, leftChild, start, mid);
    const rightSum = this.sumRange(L, R, rightChild, mid + 1, end);
    return leftSum + rightSum;
  }
}

// Usage example
const st = new SegmentTree([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(st.sumRange(0, 3)); // 9
console.log(st.sumRange(2, 5)); // 19
console.log(st.sumRange(4, 7)); // 22

// Update: set arr[2] to 10
st.update(2, 10);
console.log(st.sumRange(0, 3)); // 3 + 1 + 10 + 1 = 15
console.log(st.sumRange(2, 5)); // 10 + 1 + 5 + 9 = 25

Both update and sumRange operations run in O(log n) time, and the tree uses O(n) space. The Segment Tree is more verbose than the Fenwick Tree but offers greater flexibility for different types of range queries.

Approach 5: Iterative Segment Tree

The recursive Segment Tree above is clear but has function call overhead. For performance-critical applications, an iterative (bottom-up) Segment Tree is preferred. This version uses exactly 2n space and avoids recursion entirely.

class IterativeSegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(2 * this.n);
    // Place leaves at indices n to 2n-1
    for (let i = 0; i < this.n; i++) {
      this.tree[this.n + i] = arr[i];
    }
    // Build internal nodes from bottom up
    for (let i = this.n - 1; i > 0; i--) {
      this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
    }
  }

  // Update the element at 'index' to 'value'
  update(index, value) {
    let pos = this.n + index;
    this.tree[pos] = value;
    for (let i = pos >> 1; i >= 1; i >>= 1) {
      this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
    }
  }

  // Query the sum of elements from L to R (inclusive)
  sumRange(L, R) {
    let sum = 0;
    let l = this.n + L;
    let r = this.n + R;
    while (l <= r) {
      if (l % 2 === 1) {
        sum += this.tree[l];
        l++;
      }
      if (r % 2 === 0) {
        sum += this.tree[r];
        r--;
      }
      l >>= 1;
      r >>= 1;
    }
    return sum;
  }
}

// Usage example
const ist = new IterativeSegmentTree([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(ist.sumRange(0, 3)); // 9
console.log(ist.sumRange(2, 5)); // 19
console.log(ist.sumRange(4, 7)); // 22

ist.update(2, 10);
console.log(ist.sumRange(0, 3)); // 15
console.log(ist.sumRange(2, 5)); // 25

This iterative version is not only faster in practice but also more concise. It's the implementation you'll often see in competitive programming solutions.

Comparing the Approaches

Here's a summary of all the approaches we've covered:

Best Practices

Choose the Right Data Structure

Don't reach for a Segment Tree when a simple prefix sum array will do. If your array is immutable, the prefix sum approach gives you O(1) queries with minimal code. Reserve Fenwick Trees and Segment Trees for cases where updates are required.

Handle Edge Cases

Always test your implementation with edge cases: empty ranges (L === R), full array ranges (L === 0, R === n - 1), single-element arrays, and arrays with negative numbers. These cases often reveal off-by-one errors.

// Edge case testing
const test = new FenwickTree([5]);
console.log(test.sumRange(0, 0)); // 5

const test2 = new FenwickTree([-3, 5, -2, 8, -1]);
console.log(test2.sumRange(0, 4)); // 7
console.log(test2.sumRange(1, 3)); // 11

Be Mindful of Integer Overflow

JavaScript uses 64-bit floating-point numbers for all numeric values, which can safely represent integers up to 2^53 - 1. For most practical purposes, this is sufficient. However, if you're working with extremely large numbers or need exact integer arithmetic, consider using BigInt.

Use 1-Based Indexing for Fenwick Trees

Fenwick Trees fundamentally require 1-based indexing because the algorithm relies on the lowest set bit, and index 0 has no set bits. Always convert your 0-based array indices to 1-based when interacting with the tree, as shown in the implementation above.

Consider Lazy Propagation for Range Updates

If you need to update a range of elements at once (e.g., "add 5 to all elements from index 2 to 6"), a basic Segment Tree or Fenwick Tree won't suffice. You'll need a Segment Tree with lazy propagation, which defers updates to child nodes until they're actually needed. This keeps both range updates and range queries at O(log n) time.

Practical Example: Analyzing Stock Prices

Let's put everything together with a practical example. Imagine you're building a tool to analyze stock price movements. You have daily price changes (which can be positive or negative), and you want to quickly answer questions like "What's the net change from day 3 to day 7?" while also allowing real-time updates as new data comes in.

class StockAnalyzer {
  constructor(dailyChanges) {
    this.ft = new FenwickTree(dailyChanges);
    this.changes = [...dailyChanges];
  }

  // Get net price change between day L and day R (inclusive)
  getNetChange(L, R) {
    return this.ft.sumRange(L, R);
  }

  // Correct a day's change (e.g., fixing a data entry error)
  correctDay(day, newChange) {
    const delta = newChange - this.changes[day];
    this.changes[day] = newChange;
    this.ft.update(day, delta);
  }

  // Add a new day's change
  addDay(change) {
    // Extend the Fenwick Tree (simplified: rebuild for this example)
    this.changes.push(change);
    this.ft = new FenwickTree(this.changes);
  }
}

// Simulate 8 days of stock price changes
const analyzer = new StockAnalyzer([10, -5, 20, -15, 30, -10, 25, -5]);

console.log("Net change days 0-3:", analyzer.getNetChange(0, 3));   // 10
console.log("Net change days 2-5:", analyzer.getNetChange(2, 5));   // 25
console.log("Net change days 0-7:", analyzer.getNetChange(0, 7));   // 50

// Fix a data entry error on day 1: was -5, should be -8
analyzer.correctDay(1, -8);
console.log("After correction, days 0-3:", analyzer.getNetChange(0, 3)); // 7

This example demonstrates how the Fenwick Tree enables both fast queries and fast updates in a realistic scenario. The correctDay method shows how to handle point updates by computing the delta and applying it to the tree.

Conclusion

The Range Sum Query problem is a cornerstone of algorithmic problem-solving that teaches essential concepts in data structure design. We've journeyed from the naive O(n) per-query approach through the elegant O(1) prefix sum solution for immutable arrays, and finally to the O(log n) Fenwick Tree and Segment Tree solutions that handle dynamic updates efficiently. The key takeaway is that the right data structure depends on your specific use case: use prefix sums when the array never changes, Fenwick Trees when you need point updates with minimal code, and Segment Trees when you need flexibility for different query types or range updates. By mastering these techniques, you'll be well-equipped to tackle not just range sum queries, but a wide family of range query problems that appear frequently in real-world applications and technical interviews alike.

🛠 Tools from DevBytes

Inventory Tracker Pro — Excel inventory system, low-stock alerts · $19
AI Dev Kit for Mac — local AI dev environment templates · $9.99
KeyMapper for Mac — custom keyboard shortcut toolkit · $7.99

← Back to all articles