Segment & Fenwick Trees

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)$ — a handful of steps even for millions of elements.

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">{{hint_p}}</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">{{btn_query}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</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; }

// Code not found

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)$ 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.

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)$ time and $O(n)$ space (about 2n–4n nodes).
• Point update and range query are each $O(\log n)$: the tree has height ⌈$\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)$ 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)$ 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)$.

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.

"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)$ 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.

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)$ — 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.