Introduction

You have an array of numbers and two things to do over and over: change one value, and ask for the sum of a range. Sounds trivial — and with a plain array you can always do one of them instantly. The trouble is the other one.

Keep the raw array and an update is one write, but a range sum means walking every element in the range: slow when the array is huge and the ranges are wide. Keep a table of prefix sums instead and any range sum is a single subtraction — but now changing one value forces you to rebuild half the table.

That tension between fast reads and fast writes is the whole story. Segment trees and Fenwick trees (also called binary indexed trees) escape it: they answer both a point update and a range query in O(log⁡n)O(\log n) — a handful of steps even for millions of elements.

Build the Tree

Below is an 8-element array sitting under a segment tree. Each internal node stores the sum of the leaves beneath it, so the root holds the total of everything.

<p class="hint">An 8-element array sits at the bottom; each node above stores the <b>sum</b> of the leaves beneath it. <b>Click a leaf</b> to add 1 to it — only the nodes on the path to the root change. Then pick a range and press <b>Query</b>: the answer comes from a few covering nodes, not from scanning the cells.</p>
<div id="tree" class="tree"></div>
<div class="controls">
  <label>Range&nbsp;<select id="lo"></select> … <select id="hi"></select></label>
  <button id="query" type="button">Query sum</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Click a leaf to update, or run a range query.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.tree { display: flex; flex-direction: column; gap: 8px; align-items: stretch; }
.level { display: flex; gap: 6px; justify-content: center; }
.node { flex: 1 1 0; min-width: 0; height: 38px; display: flex; flex-direction: column;
        align-items: center; justify-content: center; border-radius: 8px;
        background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3;
        font: 700 14px ui-monospace, monospace; transition: all .25s; }
.node small { font: 500 9px system-ui, sans-serif; color: #6b7c8f; }
.node.leaf { cursor: pointer; background: #d7e3ee; }
.node.leaf:hover { background: #c4d6e6; }
.node.touched { background: #ffd166; border-color: #e0a92e; color: #5a3d00; }
.node.cover { background: #06d6a0; border-color: #04a87c; color: #003124; }
.status { font-size: .98rem; font-weight: 600; margin: .7rem 0 0; min-height: 1.4em; color: #1d3557; }
.controls { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; margin-top: .8rem; }
select { font: 600 13px ui-monospace, monospace; padding: .25rem .4rem; border-radius: 6px; border: 1px solid #adb1b8; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Segment tree over n = 8 leaves stored in a 1-indexed array of size 2n.
// tree[1] is the root; node i has children 2i and 2i+1; leaves are tree[n..2n-1].
// build O(n); point update and range query each O(log n): they touch at most a
// constant number of nodes per level, and the tree has height ceil(log2 n).
const n = 8;
let arr = [3, 1, 4, 1, 5, 9, 2, 6];
const tree = new Array(2 * n).fill(0);

function build() {
  for (let i = 0; i < n; i++) tree[n + i] = arr[i];
  for (let i = n - 1; i >= 1; i--) tree[i] = tree[2 * i] + tree[2 * i + 1];
}
// Update leaf index p (0-based) to value v; returns the set of node ids touched.
function update(p, v) {
  const path = new Set();
  let i = p + n; tree[i] = v; path.add(i);
  for (i = Math.floor(i / 2); i >= 1; i = Math.floor(i / 2)) {
    tree[i] = tree[2 * i] + tree[2 * i + 1]; path.add(i);
  }
  return path;
}
// Range sum over [l, r] inclusive (0-based); returns {sum, cover:Set of node ids}.
function query(l, r) {
  let lo = l + n, hi = r + n + 1, sum = 0; const cover = new Set();
  while (lo < hi) {
    if (lo & 1) { sum += tree[lo]; cover.add(lo); lo++; }
    if (hi & 1) { hi--; sum += tree[hi]; cover.add(hi); }
    lo >>= 1; hi >>= 1;
  }
  return { sum, cover };
}

// ---- rendering ----
// Place node ids by level: level d holds ids [2^d .. 2^(d+1)-1]. n=8 => depths 0..3.
const depth = Math.log2(n); // 3
function render(highlight) {
  const el = document.getElementById('tree'); el.innerHTML = '';
  for (let d = 0; d <= depth; d++) {
    const row = document.createElement('div'); row.className = 'level';
    const start = 1 << d, end = (1 << (d + 1)) - 1;
    for (let id = start; id <= end; id++) {
      const node = document.createElement('div');
      const isLeaf = id >= n;
      node.className = 'node' + (isLeaf ? ' leaf' : '');
      if (highlight && highlight.touched && highlight.touched.has(id)) node.classList.add('touched');
      if (highlight && highlight.cover && highlight.cover.has(id)) node.classList.add('cover');
      node.innerHTML = tree[id] + (isLeaf ? '<small>a[' + (id - n) + ']</small>' : '');
      if (isLeaf) {
        const p = id - n;
        node.addEventListener('click', () => {
          const touched = update(p, tree[id] + 1); arr[p] = tree[id];
          render({ touched });
          setStatus(fmt('Updated a[%p%] = %v% — touched %size% of %v2% nodes (about log₂ %n% + 1).', { p: p, v: tree[id], size: touched.size, v2: 2 * n - 1, n: n }));
        });
      }
      row.appendChild(node);
    }
    el.appendChild(row);
  }
}
function setStatus(t) { document.getElementById('status').textContent = t; }

function fillSelects() {
  const lo = document.getElementById('lo'), hi = document.getElementById('hi');
  for (let i = 0; i < n; i++) {
    lo.add(new Option(i, i)); hi.add(new Option(i, i));
  }
  lo.value = 2; hi.value = 6;
}
function runQuery() {
  let l = +document.getElementById('lo').value, r = +document.getElementById('hi').value;
  if (l > r) { const t = l; l = r; r = t; document.getElementById('lo').value = l; document.getElementById('hi').value = r; }
  const { sum, cover } = query(l, r);
  render({ cover });
  setStatus(fmt('sum(a[%l%..%r%]) = %sum% from %size% covering node(s) — not %v%%v2% element reads.', { l: l, r: r, sum: sum, size: cover.size, v: r - l, v2: 1 }));
  console.log('query', l, r, '=>', sum, 'cover ids', [...cover]);
}

function reset() {
  arr = [3, 1, 4, 1, 5, 9, 2, 6]; build(); render(null);
  setStatus('Click a leaf to update, or run a range query.');
}

document.getElementById('query').addEventListener('click', runQuery);
document.getElementById('reset').addEventListener('click', reset);
fillSelects(); build(); render(null);
Result
Console

Click a leaf to bump its value, and watch: only the nodes on the path from that leaf up to the root light up and change — about log⁡2(n)\log_{2}(n) of them, not the whole tree. Then pick a range and press Query; the answer is assembled from a few covering nodes that flash, never by scanning the range cell by cell. Compare the highlighted-node count against the array's length: that gap is the speed-up.

The Real Complexity

These are solved problems — not open questions, but engineered data structures with proven, tight bounds.

  • Building a segment tree over n elements takes O(n)O(n) time and O(n)O(n) space (about 2n–4n nodes).
  • Point update and range query are each O(log⁡n)O(\log n): the tree has height ⌈log⁡2\log_{2} n⌉, and both operations touch at most a constant number of nodes per level.
  • Why it works: any range [l, r] decomposes into O(log⁡n)O(\log n) canonical segments — the maximal precomputed nodes that tile it — so the query never inspects individual elements.
  • Fenwick / binary indexed trees (introduced by Peter Fenwick in 1994) give the same O(log⁡n)O(\log n) prefix-sum update and query using a single array and the bit trick i & (-i) to hop between responsibility ranges. They are smaller and faster in practice, though limited to invertible operations like sums.
  • Lazy propagation extends segment trees to range updates (add a value to a whole interval) while keeping every operation O(log⁡n)O(\log n).

The deep point: a logarithmic structure converts an unavoidable linear scan into a few hops. This is the same divide-and-conquer that makes sorting and search fast — and it sidesteps entirely the intractability lurking in problems like P vs NP.

Where It Matters

"Aggregate over a moving range of changing data" shows up everywhere, and these trees are the standard answer:

  • Competitive programming: range-sum, range-min/max and order-statistics problems are bread-and-butter, and Fenwick trees are the go-to for counting inversions.
  • Databases and analytics: indexes and materialized aggregates that must stay current as rows change rely on the same logarithmic-update idea, closely related to query optimization.
  • Computational geometry: sweep-line algorithms count points in ranges, measure unions of rectangles, and answer stabbing queries with segment and interval trees.
  • Graphics and signals: prefix-sum / summed-area tables give O(1)O(1) box filters, the static cousin of the same idea.

The unifying lesson: when a problem reduces to repeated associative aggregation over intervals, you almost never need to look at every element.

Conclusion

The flat array forced a false choice: cheap updates or cheap range queries, never both. By storing partial answers in a balanced tree, segment and Fenwick trees give you both in O(log⁡n)O(\log n) — a few hops instead of a full scan — with a clean correctness proof and no hidden caveats.

They are a small monument to a big idea: precompute just enough structure that every later question collapses to a logarithmic walk. Master them once and you will reach for the same move across databases, geometry, and contests — wherever data changes and ranges keep getting asked about.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/segment-trees/Content licensed under CC BY-NC 4.0.