DSA DSA In Depth
0%
From-Scratch Build

Fenwick Range-Update Range-Query Tree & O(log n) Binary Lifting

A Binary Indexed Tree (Fenwick Tree) featuring O(n) linear construction, dual-array range-update/range-query (RURQ), and O(log n) prefix binary lifting.

~35 min Intermediate Lessons: Fenwick Trees (Binary Indexed Trees): lowbit Geometry, Point Updates & Range Updates, Fenwick Trees (Binary Indexed Trees): lowbit Geometry, Point Updates & Range Updates, Twos-Complement Arithmetic, Bitmasks, Brian Kernighan's Trick & XOR, Segment Trees over Monoids: Recursive vs Iterative (ZKW) Bottom-Up Implementation, Lazy Propagation & Segment Tree Beats (Ji Driver Segment Tree for Range Chmin/Chmax), Disjoint & Standard Sparse Tables: O(1) Idempotent Range Minimum Query (RMQ)
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Two's-Complement Indexing & O(n) Construction

A Fenwick Tree (Binary Indexed Tree) stores partial range aggregates keyed by the lowest set bit $\text{lsb}(i) = i \mathbin{\&} (-i)$ in two's-complement arithmetic:

  • Query (_sum): strips the lowest set bit via i -= i & -i to sum $O(\log n)$ disjoint power-of-two intervals covering $[1..k]$.
  • Update (_add): adds the lowest set bit via i += i & -i to update all ancestor intervals covering index $i$.
  • $O(n)$ Build: instead of calling _add $n$ times ($O(n \log n)$), each index $i$ propagates its accumulated value only to its immediate parent $j = i + (i \mathbin{\&} -i)$ in a single $O(n)$ forward sweep.

Range-Update Range-Query (RURQ) via Dual BITs

Let $D[i] = A[i] - A[i-1]$ be the difference array. After adding $\Delta$ to $[L, R]$, the prefix sum $\sum_{i=1}^k A[i]$ expands algebraically to:

$$\sum_{i=1}^{k} A[i] = \sum_{i=1}^{k} D[i] \cdot (k - i + 1) = k \sum_{i=1}^{k} D[i] - \sum_{i=1}^{k} Di$$

By maintaining $\text{BIT}_1[i] = D[i]$ and $\text{BIT}_2[i] = Di$, both rangeAdd(l, r, delta) and rangeSum(l, r) execute in $O(\log n)$ time using only two flat Float64Array buffers.

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: O(n) Linear-Time Construction

  • Core Mechanical Concept: O(n) Linear-Time Construction
  • Target Module: index.js (Step1)
  • Engineering Specification: Initialize _b1 and _b2 from the initial array in $O(n)$ time by propagating each node i directly to its immediate tree parent parent = i + (i & -i).
  • Verification Invariant: verifies Step 1: O(n) Linear-Time Construction

Step 2: Two's-Complement LSB Traversal (_add & _sum)

  • Core Mechanical Concept: Two's-Complement LSB Traversal (_add & _sum)
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement _add(bit, idx, delta) stepping i += i & -i and _sum(bit, idx) stepping i -= i & -i.
  • Verification Invariant: verifies Step 2: Two's-Complement LSB Traversal (_add & _sum)

Step 3: Dual-BIT Range Add & Range Sum

  • Core Mechanical Concept: Dual-BIT Range Add & Range Sum
  • Target Module: index.js (Step3)
  • Engineering Specification: Use the algebraic identity $\sum_{i=1}^k A[i] = k \sum_{i=1}^k D[i] - \sum_{i=1}^k Di$ to support both range additions and range sum queries in $O(\log n)$ time.
  • Verification Invariant: verifies Step 3: Dual-BIT Range Add & Range Sum

Step 4: Prefix Binary Lifting

  • Core Mechanical Concept: Prefix Binary Lifting
  • Target Module: index.js (Step4)
  • Engineering Specification: Implement lowerBoundPrefix(targetSum) by stepping down powers of two from the highest bit of n to find the first prefix reaching targetSum.
  • Verification Invariant: verifies Step 4: Prefix Binary Lifting

Asymptotic & Memory Layout Guarantees

  • Category: Range Queries & Trees
  • Difficulty: Intermediate (~35 minutes)
  • Key Architectural Highlights:
    • O(n) linear-time tree construction via immediate parent propagation i + (i & -i)
    • Dual-BIT algebraic decomposition enabling O(log n) range add and O(log n) range sum
    • O(log n) binary lifting on the Fenwick tree to find the lowerBound prefix threshold in a single pass
  • Tags & Primitives: Fenwick Tree, Binary Indexed Tree, Range Update Range Query, Binary Lifting, Two-s Complement

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.