DSA Lab
Segment tree
A segment tree stores the sum of every half, quarter, eighth… of an array in a binary tree. Any range sum can then be built from a few stored sums, and changing one value fixes only one path.
Segment tree: how it works
In this tool: range sums and updates in O(log n). Put in your own values and watch it change. Each operation runs one step at a time and says in plain words what happened, with its calculation worked out. The code is shown in Python, C, C++ or Java with the line that just ran marked, and an Understand it panel gives the idea, why it works, the cost of each operation, common mistakes and a short quiz.
Lessons that use it
- Segment trees and Fenwick trees (Data Structures)Answer range-sum questions and change single values in O(log n) each, where a plain array or prefix sums make one of the two slow.
- Prefix sums (Competitive)One pass of preparation answers every range-sum question in O(1): the most useful trick in contests.