Repository: cockroachdb/pebble
Pull request #3904 (2024-08-29 04:10:08)

treesteps: infrastructure for visualization of operations on trees
This commit introduces a new piece of infrastructure that allows
generating step-by-step illustrations of how an operation propagates
down a hierarchical structure and how the state of the nodes in the
structure changes.

The infrastructure is designed so that no extra arguments need to be
plumbed through the operation stack. We achieve that by maintaining a
global list of nodes that are part of a hierarchy for which we are
"recording".

See `tree_steps_test.go` for sample usage and `testdata/segment_tree`
for sample recordings.

The goal is to integrate this with the iterator stack (in particular
the `mergingIter`, `levelIter`, and sstable iterators). The
integration will be conditioned on `invariants.Enabled` so we won't
add any overhead in production.

cockroach-teamcity: 

<!-- Reviewable:start -->
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/cockroachdb/pebble/3904)
<!-- Reviewable:end -->

RaduBerinde: Friendly ping.. This is only testing infra so it doesn't need too much scrutiny. Might want to take a look at the test to see how it integrates.

Patch:
diff --git a/internal/treesteps/data.go b/internal/treesteps/data.go
new file mode 100644
index 00000000..b6a0ac9b
--- /dev/null
+++ b/internal/treesteps/data.go
@@ -0,0 +1,119 @@
+// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+package treesteps
+
+import (
+	"bytes"
+	"compress/zlib"
+	"encoding/base64"
+	"encoding/json"
+	"fmt"
+	"net/url"
+	"strings"
+
+	"github.com/cockroachdb/pebble/internal/treeprinter"
+)
+
+// Steps contains the result of a recording: the full details of the hierarchy
+// for each step.
+type Steps struct {
+	Name  string
+	Steps []Step `json:"steps"`
+}
+
+// Step contains the tree for a single step in a recording.
+type Step struct {
+	Name string   `json:"name"`
+	Root TreeNode `json:"tree"`
+}
+
+// TreeNode is a node in the tree for a step in a recording.
+type TreeNode struct {
+	Name       string      `json:"name"`
+	Properties [][2]string `json:"props"`
+	Ops        []string    `json:"ops"`
+	Children   []TreeNode  `json:"children"`
+}
+
+// String returns the steps as a string (using treeprinter).
+func (s Steps) String() string {
+	var buf strings.Builder
+	for step := range s.Steps {
+		if len(s.Steps) > 1 {
+			fmt.Fprintf(&buf, "step %d/%d:\n", step+1, len(s.Steps))
+		}
+		out := s.Steps[step].Root.String()
+		if len(s.Steps) > 1 {
+			for _, l := range strings.Split(strings.TrimSpace(out), "\n") {
+				fmt.Fprintf(&buf, "  %s\n", l)
+			}
+		} else {
+			buf.WriteString(out)
+		}
+	}
+	return buf.String()
+}
+
+func (t *TreeNode) String() string {
+	tp := treeprinter.New()
+	t.print(tp)
+	return tp.String()
+}
+
+func (t *TreeNode) print(parent treeprinter.Node) {
+	name := t.Name
+	for i := range t.Ops {
+		name += fmt.Sprintf("  ← %s", t.Ops[i])
+	}
+	n := parent.Child(name)
+	for _, p := range t.Properties {
+		n.Childf("%s: %s", p[0], p[1])
+	}
+	for i := range t.Children {
+		t.Children[i].print(n)
+	}
+}
+
+// URL for a visualization of the steps. The URL contains the encoded and
+// compressed data as the URL fragment.
+func (s Steps) URL() url.URL {
+	// TODO(radu): ideally we would encode Steps and have a graphical
+	// visualization. For now, we generate and encode the ASCII trees.
+	var output struct {
+		Name      string
+		StepNames []string
+		Steps     []string
+	}
+	output.Name = s.Name
+	output.StepNames = make([]string, len(s.Steps))
+	output.Steps = make([]string, len(s.Steps))
+	for i := range s.Steps {
+		output.StepNames[i] = s.Steps[i].Name
+		output.Steps[i] = s.Steps[i].Root.String()
+	}
+
+	var jsonBuf bytes.Buffer
+	if err := json.NewEncoder(&jsonBuf).Encode(&output); err != nil {
+		panic(err)
+	}
+	var compressed bytes.Buffer
+	encoder := base64.NewEncoder(base64.URLEncoding, &compressed)
+	compressor := zlib.NewWriter(encoder)
+	if _, err := jsonBuf.WriteTo(compressor); err != nil {
+		panic(err)
+	}
+	if err := compressor.Close(); err != nil {
+		panic(err)
+	}
+	if err := encoder.Close(); err != nil {
+		panic(err)
+	}
+	return url.URL{
+		Scheme:   "https",
+		Host:     "raduberinde.github.io",
+		Path:     "treesteps/decode.html",
+		Fragment: compressed.String(),
+	}
+}
diff --git a/internal/treesteps/node_state.go b/internal/treesteps/node_state.go
new file mode 100644
index 00000000..60f6f8ef
--- /dev/null
+++ b/internal/treesteps/node_state.go
@@ -0,0 +1,60 @@
+// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+package treesteps
+
+import (
+	"fmt"
+	"sync"
+	"sync/atomic"
+)
+
+type nodeState struct {
+	recording *Recording
+	node      Node
+	name      string
+
+	// ops currently running for this node.
+	ops []*Op
+}
+
+var mu struct {
+	sync.Mutex
+
+	recordingInProgress atomic.Bool
+	nodeMap             map[Node]*nodeState
+}
+
+func buildTree(n *nodeState) TreeNode {
+	var t TreeNode
+	info := n.node.TreeStepsNode()
+	n.name = info.name
+	t.Name = info.name
+	t.Properties = info.properties
+	if len(n.ops) > 0 {
+		t.Ops = make([]string, len(n.ops))
+		for i := range t.Ops {
+			t.Ops[i] = n.ops[i].details
+			if n.ops[i].state != "" {
+				t.Ops[i] += " " + n.ops[i].state
+			}
+		}
+	}
+	for i := range info.children {
+		c := nodeStateLocked(n.recording, info.children[i])
+		t.Children = append(t.Children, buildTree(c))
+	}
+	return t
+}
+
+func nodeStateLocked(w *Recording, n Node) *nodeState {
+	ns, ok := mu.nodeMap[n]
+	if !ok {
+		ns = &nodeState{recording: w, node: n}
+		mu.nodeMap[n] = ns
+	} else if w != ns.recording {
+		panic(fmt.Sprintf("node %v part of multiple recordings", n))
+	}
+	return ns
+}
diff --git a/internal/treesteps/tree_steps.go b/internal/treesteps/tree_steps.go
new file mode 100644
index 00000000..8bc037a5
--- /dev/null
+++ b/internal/treesteps/tree_steps.go
@@ -0,0 +1,231 @@
+// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+package treesteps
+
+import (
+	"fmt"
+	"reflect"
+	"slices"
+	"strings"
+	"unicode"
+
+	"github.com/cockroachdb/pebble/internal/treeprinter"
+)
+
+// StartRecording starts a new recording that captures step-by-step propagation
+// of operations and changes in a hierarchical structure.
+//
+// Each node in the structure must implement the TreeStepsNode method, which
+// returns information about the current state of the node and a list of its
+// children. For every operation or sub-operation on a node, StartOpf and
+// FinishOpf must be called. Calling Finish() on the Recording will return all
+// the collected information (which can be presented as text or as a link to a
+// visualization).
+//
+// It is not legal to start a recording that involves the same node as another
+// in-progress recording (this applies to all nodes in the hierarchy).
+//
+// See SegmentTree in tree_steps_test.go for an example.
+func StartRecording(root Node, name string) *Recording {
+	mu.Lock()
+	defer mu.Unlock()
+	mu.recordingInProgress.Store(true)
+	w := &Recording{name: name}
+
+	if mu.nodeMap == nil {
+		mu.nodeMap = make(map[Node]*nodeState)
+	}
+	w.root = nodeStateLocked(w, root)
+	w.stepLockedf("initial")
+	return w
+}
+
+// NodeUpdated can be used to trigger a new step in any recording that involves
+// the given node. It can be used when the state of the node changed in a
+// significant way. The reason is optional and will show up in the step
+// description.
+func NodeUpdated(n Node, reason string) {
+	if !mu.recordingInProgress.Load() {
+		return
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	if ns, ok := mu.nodeMap[n]; ok {
+		if reason == "" {
+			reason = " updated"
+		} else {
+			reason = ": " + reason
+		}
+		ns.recording.stepLockedf("node %s%s", firstWord(ns.name), reason)
+	}
+}
+
+// Node must be implemnented by every node in the hierarchy.
+type Node interface {
+	TreeStepsNode() NodeInfo
+}
+
+// NodeInfo contains the information that we present for each node.
+type NodeInfo struct {
+	name       string
+	properties [][2]string
+	children   []Node
+}
+
+// NodeInfof returns a NodeInfo with the name initialized with a formatted
+// string.
+func NodeInfof(format string, args ...any) NodeInfo {
+	return NodeInfo{name: fmt.Sprintf(format, args...)}
+}
+
+// AddPropf adds a property to the NodeInfo.
+func (ni *NodeInfo) AddPropf(key string, format string, args ...any) {
+	ni.properties = append(ni.properties, [2]string{key, fmt.Sprintf(format, args...)})
+}
+
+// AddChildren adds one or more children to the NodeInfo.
+//
+// Any nil children are ignored (this includes nil pointers of any type).
+func (ni *NodeInfo) AddChildren(nodes ...Node) {
+	for _, n := range nodes {
+		if n == nil {
+			continue
+		}
+		if val := reflect.ValueOf(n); val.Kind() == reflect.Ptr && val.IsNil() {
+			continue
+		}
+		ni.children = append(ni.children, n)
+	}
+}
+
+// Recording captures the step-by-step propagation of operations. See
+// StartRecording.
+type Recording struct {
+	name  string
+	root  *nodeState
+	steps []Step
+}
+
+// Finish completes the recording and returns the recorded steps.
+func (r *Recording) Finish() Steps {
+	mu.Lock()
+	defer mu.Unlock()
+	for n, ns := range mu.nodeMap {
+		if ns.recording == r {
+			delete(mu.nodeMap, n)
+		}
+	}
+	if len(mu.nodeMap) == 0 {
+		mu.recordingInProgress.Store(false)
+	}
+	r.root = nil
+	return Steps{Name: r.name, Steps: r.steps}
+}
+
+// stpLockedf updates the tree (calling TreeStepsNode on all the nodes) and
+// saves it as a step. The formatted string is the name/description of the step.
+func (r *Recording) stepLockedf(format string, args ...any) {
+	r.steps = append(r.steps, Step{
+		Name: fmt.Sprintf(format, args...),
+		Root: buildTree(r.root),
+	})
+}
+
+// IsRecording indicates whether a recording involving a given node is currently
+// in progress. Can be used as a fast check before calling StartOpf.
+func IsRecording(n Node) bool {
+	if !mu.recordingInProgress.Load() {
+		return false
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	_, ok := mu.nodeMap[n]
+	return ok
+}
+
+// Op represents an operation that is associated with a node.
+type Op struct {
+	details   string
+	state     string
+	nodeState *nodeState
+}
+
+// StartOpf registers the start of a new operation on a node and emits a step.
+// The operation will be displayed for the given node until FinishOpf is called.
+//
+// If a recording involving the node is not currently in progress, does nothing
+// and returns nil. Other methods can be called (and do nothing) when Op is nil.
+//
+// Note: it is recommended that IsRecording() is checked first to avoid any
+// allocations (e.g. due to boxing of args) in the normal, non-recording path.
+func StartOpf(node Node, format string, args ...any) *Op {
+	mu.Lock()
+	defer mu.Unlock()
+	ns, ok := mu.nodeMap[node]
+	if !ok {
+		return nil
+	}
+	op := &Op{
+		details:   fmt.Sprintf(format, args...),
+		nodeState: ns,
+	}
+	ns.ops = append(ns.ops, op)
+	ns.recording.stepLockedf("%s on %s started", firstWord(op.details), firstWord(op.nodeState.name))
+	return op
+}
+
+// Updatef changes the state of the operation and emits a step. The state of the
+// // operation shows up after the details that were provided in StartOpf.
+func (op *Op) Updatef(format string, args ...any) {
+	if op == nil {
+		return
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	op.state = fmt.Sprintf(format, args...)
+	op.nodeState.recording.stepLockedf("%s on %s updated", firstWord(op.details), firstWord(op.nodeState.name))
+}
+
+// Finishf changes the state of the operation, emits a step, and cleans up the
+// operation.The state of the operation shows up after the details that were
+// provided in StartOpf.
+func (op *Op) Finishf(format string, args ...any) {
+	if op == nil {
+		return
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	op.state = fmt.Sprintf(format, args...)
+	op.nodeState.recording.stepLockedf("%s on %s finished", firstWord(op.details), firstWord(op.nodeState.name))
+	op.nodeState.ops = slices.DeleteFunc(op.nodeState.ops, func(o *Op) bool { return o == op })
+}
+
+func firstWord(str string) string {
+	for i, r := range str {
+		if unicode.IsSpace(r) || strings.ContainsRune("()[]{}:", r) {
+			return str[:i]
+		}
+	}
+	return str
+}
+
+// TreeToString returns a string representation of the current state of a Node
+// tree.
+func TreeToString(n Node) string {
+	tp := treeprinter.New()
+	treePrint(n, tp)
+	return tp.String()
+}
+
+func treePrint(n Node, tp treeprinter.Node) {
+	ni := n.TreeStepsNode()
+	tpNode := tp.Child(ni.name)
+	for _, prop := range ni.properties {
+		tpNode.Childf("%s: %s", prop[0], prop[1])
+	}
+	for _, child := range ni.children {
+		treePrint(child, tpNode)
+	}
+}


Test patch:
diff --git a/internal/treesteps/testdata/segment_tree b/internal/treesteps/testdata/segment_tree
new file mode 100644
index 00000000..f5848286
--- /dev/null
+++ b/internal/treesteps/testdata/segment_tree
@@ -0,0 +1,738 @@
+init range=4
+----
+n0
+ ├── range: [1, 4]
+ ├── sum: 0
+ ├── n1
+ │    ├── range: [1, 2]
+ │    ├── sum: 0
+ │    ├── n3
+ │    │    ├── range: [1, 1]
+ │    │    └── sum: 0
+ │    └── n4
+ │         ├── range: [2, 2]
+ │         └── sum: 0
+ └── n2
+      ├── range: [3, 4]
+      ├── sum: 0
+      ├── n5
+      │    ├── range: [3, 3]
+      │    └── sum: 0
+      └── n6
+           ├── range: [4, 4]
+           └── sum: 0
+
+add x=3 delta=1
+----
+step 1/10:
+  n0
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 2/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 3/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 4/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5  ← add(3, 1)
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 5/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5  ← add(3, 1)
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 6/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5  ← add(3, 1) done
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 7/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 8/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1) done
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 9/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 10/10:
+  n0  ← add(3, 1) done
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+
+add x=2 delta=1
+----
+step 1/10:
+  n0
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 2/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 3/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 4/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4  ← add(2, 1)
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 5/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4  ← add(2, 1)
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 6/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4  ← add(2, 1) done
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 7/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 8/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1) done
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 9/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 10/10:
+  n0  ← add(2, 1) done
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+
+sum x1=1 x2=3
+----
+step 1/9:
+  n0
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 2/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 3/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1  ← sum(1, 3)
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 4/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1  ← sum(1, 3) = 1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 5/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 6/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5  ← sum(1, 3)
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 7/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5  ← sum(1, 3) = 1
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 8/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3) = 1
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 9/9:
+  n0  ← sum(1, 3) = 2
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+
+add x=3 delta=10 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzsmLFOwzAYhHee4uQJpAyO0zLkIVjK1nqwZFMikb9Vk04IqWJgZsjI0-VJUFpK3cRGCIEo6B97vp7u__U5inIvrkzpRC4mbl46qnG9cg7GWpGISe2W3Wkl8qkoqKgLcycSYazFgkASVW1WtbOepgLa2NNoYR1onKNal1gvrelbbwoqqlvPq2JeNfTKmFcevHo313YmkjNC27y0zaZtNlgZmrsc0zTBSB-dVOsyhzqSKN3-fAQQjlA6ZNgmBf9Kma_Gc1Md8DV-vPQN-xMaHVSEw9VxaQSid83fM7uVRMKytyUiMn9Pp_FBi8yeJcj0wDWo16tNl3stUnTkFw3NLGfUESaB9um5uxrnWYJUXjA7zA6z8zvsBPbJLDFLp8ZSPJrZYrZOkC2Gi-EKwQW7IMeEMWFfIuzn3rOYpj9MU--hwkh9jFTKTH3bR4R_gs_-BjFDzNBnGNIPZ68BAAD__6rCZP4=
+
+sum x1=1 x2=3 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzslrFKxEAQhnufYphKYYvdJGcR8BVszu5ui4DrGTCjZJNKhMPC2iKlT5cnkVy8S2Jm4YoDhZsy30x-ZocPdl_xNiscprh0m8JRBXelc-DrAhUuK_fSVT2mK8wpr_LsCRX6uoBnAtLgq6ys3P2IGZY95JT7xwmMmMYFy9ifGagHaPvZd3OTXhO0zVfbbNtmC2VGG5fCyihI7KTi6yIFE00Ymd3nOwDwGZHlGvoorkLxmIZzjWX6mnG8HjfsK5QMFPjwaDo0MNH95IfMbiWBsPhni8Cd38wLtBhY4PCxgtjOuppQ8mHK6z0LjJqMR-VOrdeECkkDtB-fHbo0CuIrsUfs-SN7uCyRSWQ6hUxww1shQolQcrcda898nyKTyPT_ZApGi1vi1mnd6h4WRgQ7c8F-WXCG12G3gUi0kuf5kQrZt4vvAAAA___3jnU-
+
+init range=8
+----
+n0
+ ├── range: [1, 8]
+ ├── sum: 0
+ ├── n1
+ │    ├── range: [1, 4]
+ │    ├── sum: 0
+ │    ├── n3
+ │    │    ├── range: [1, 2]
+ │    │    ├── sum: 0
+ │    │    ├── n7
+ │    │    │    ├── range: [1, 1]
+ │    │    │    └── sum: 0
+ │    │    └── n8
+ │    │         ├── range: [2, 2]
+ │    │         └── sum: 0
+ │    └── n4
+ │         ├── range: [3, 4]
+ │         ├── sum: 0
+ │         ├── n9
+ │         │    ├── range: [3, 3]
+ │         │    └── sum: 0
+ │         └── n10
+ │              ├── range: [4, 4]
+ │              └── sum: 0
+ └── n2
+      ├── range: [5, 8]
+      ├── sum: 0
+      ├── n5
+      │    ├── range: [5, 6]
+      │    ├── sum: 0
+      │    ├── n11
+      │    │    ├── range: [5, 5]
+      │    │    └── sum: 0
+      │    └── n12
+      │         ├── range: [6, 6]
+      │         └── sum: 0
+      └── n6
+           ├── range: [7, 8]
+           ├── sum: 0
+           ├── n13
+           │    ├── range: [7, 7]
+           │    └── sum: 0
+           └── n14
+                ├── range: [8, 8]
+                └── sum: 0
+
+add x=6 delta=10 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzs2rFu2zAQBuC9T3Hg1AIaRMmyXT1El3RLNAggmwqozoElT0WBoEPnDhr7dHqSQmkcSyRPatEWSZx_Msw73IFH6rMGf1bvytqqXF3Y69pyS-_31lJpjIrURWtvhmij8ktVcdVW5ScVqdIY2jFxTE1b7ltrRmtJYC0LrOlxIu-MHZZyag41HW5M6SV_qLhqPo6yMyk583PFwoG6sZQbn3KLX6O5GwvHV0x996PvbvvulvYlX9ucLnVE22ISaQ51TtNk1ndfvxJRuMSqCCWMKjkRTserct2kmMnzy7tdNoGg3EyHmt1_dEs9jwm89YIU7pgEt0dL_R4arU6rQod0ejA0Pz4nzG-9kDC6NKLUb7MwOGefrN2YsKdVYE_yzB7KJ1csVczunwBpPO5cstOaMJAsonUhZrmF3UurtReT-2R-H2nw4XNhnTgxYUzrwKakwbuHuz6uCbU34yOYPQf3MHTqRIRRbSLauB1mB-Xdz9UkImxk621EGNHAeEzUf_s-_IS9Xkek4zcAGkADaAANoH9jUN79BNAAeu7OA-i_AzrwMAgdADbABtgAG2CfK9hyaQAOwAE4AAfgAPwRAV_YnzBGgA7QAbp85wE6QD9L0DVEh-gQHaJD9EcTncyOLVgH62AdrIP1P2FdPyXXQTgIB-Eg_OUQHnpzheNwHI7DcTj-JBzX_-1_hzAbZsNsmA2zZbOdF2TA7Z4H4H6WcGvIDbnPSm4gDaSfAdLHFwpIDakhNaSG1AuXNHSt_rnUxZdXPwMAAP__EYeKAA==
+
+add x=3 delta=1 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzs2r1u2zAQB_C9T3Hg1AIaREv-0kN0SbdYgwCyqYD6HFjyVBQIOnTu4LFP5ycp7Ca2TN5JQ2PUiP9TEN7hLjwyPwuGvpmP1dKbwtz5h6Xnlj6tvafKOZOYu9Y_7qONKe5NzXVbV19NYirnaMXEKTVttW6966xZYS0X1uadNV45TzwvqNksafPoqjD1c81186WTm2u5eZxrtVwb56ZabnrKLf_O5TATThdMu-3v3fZpt32idcUPvqB7m9CsPIs0m2VB9jyb7eHXH0Qk18hLKeFQKpUinHVX9bqjsicvLh92mQpBvZmVmj3_2A71fEngWRQkueNI3B4N9Ts2yk-rSofs_GCof3xBmOdRSBldllAWtxkYXLBPtmFM2VMu7Emf2bH8aMFaxfHzv4A0nsNfFQ5mfFpTJjJOaFKqWVHl8NpaG8X0RuO4kTZ6-WTYjoKYMqiJsCtp9N2tHZtMXtaU4tPuKWg3VQqyzYKIMqtpQtOwQ--koiuan0WUjcyijUgzShe8pzwl2v38tf8Me58lZD_AaBgNo2E0jB6-pNK1unqjpVogG2SDbJA9cF1BNsgG2SLZ6hEpDSE4BIfgEByC36jgQ-0AOkAH6MGtA-gA_WZBtwAdoMvFATpAB-iXBZ3cij1Uh-pQHapD9WtWPTb1kt-cQ3AIrhSH4BD85gSXH5TBOBgH42D8XxkX3zEH41fy1iHIBtkg-02SHTzWwW24Dbf7JwK3o_OF26_utg3chtEwGkbDaBgd3rpXNfr0PAyoATWgBtSA-v9DXX5_9ycAAP__KvaJtg==
+
+sum x1=2 x2=7 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzs2ztu20wQwPH-O8WA1ReABZ-SIsBXSON0NgsBYRwB0SYQpSoIYKRInUJlTqeTBHpYj-XMMkgQgJL-leGZ5Y52Z_grLPhL9GYyq6NxdF8_zWq3kLfzupZmOYvi6H5Rf95km2j8EE3ddDGdfIziqFnO5JMTl0izmMwX9buTWKrEciU2UmPvp27afPAeVoKF8nShLUy1YKY8Xaox5eGBdmjthKn6yQf6B1KCyTFY7VqxbYNLHp2sVz_Xq-f16lnmE_dUj-UhjWVUnWWa5WwsaXoWc7tfv4mIvkdRaQt2W2kZl59G7X2zKrBuu30SWOCGStIulmrF9j9WXTVfFrhRKyl6xUw9nnTVOxQqjlGjQn7eGAl3x0u7162UcXV5LHm7jHZx7WqH06SJlzPOVChnsu_ssH326Kwdy_0roF5P0k648hgzbqSMZVCZq1o7-2O7ffvkd6a2jKVsF7JmVu-MSzMvZ1zUQDmVdvWnRzsUGbzEjM2Hp13QWpEYSZfmXsa4q2EsQ79C8KZaI1qcZYyDjFoH0e4oeXRRHLlEZP39xyb0fxbL8BVGYzRGYzRGh4f0Yo3W9oJsyIZsyO4YV8i-TrID-yM4giM4giM4gksPBO86qNF5QAd0fYoBXbkwQAf0rmL_BnS5U9Yb3Qd1UNcnGdSVCwP1nqGuWnc1sKM4iqO4318Uv3jFIfuvyTZbZBREcARHcARH8J4KLncBgFEcxVH81hU_JwLJ-yI5bIffC9iG7VtiG6Mx-qKNbr8MRgHIhmzIhmzIvmKyza0RXJsBBEdwBEfw_goudyGAYRzGYRzGYbxvjEP2H5Bt9MOoheAIjuDq5CM4gvuduDLBw5UAHdABHdAB_VJB3_-7oHTPNaiDOqiDurklqIdRV6jlby0ojuIoHlDc-2YSyv128C1nX9zejGoK3uB9u3gDNVD3DOrq63-_AgAA__9MOM8F
diff --git a/internal/treesteps/tree_steps_test.go b/internal/treesteps/tree_steps_test.go
new file mode 100644
index 00000000..16b65d68
--- /dev/null
+++ b/internal/treesteps/tree_steps_test.go
@@ -0,0 +1,170 @@
+// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+package treesteps
+
+import (
+	"math/bits"
+	"testing"
+
+	"github.com/cockroachdb/datadriven"
+)
+
+// SegmentTree implements a segment tree:
+// https://en.wikipedia.org/wiki/Segment_tree
+//
+// It stores values for points in the range [1, Range]. It can efficiently Add
+// to the value of a single point, and query the Sum of any range.
+type SegmentTree struct {
+	Range int
+	Nodes []SegmentNode
+}
+
+// SegmentNode is a node in a segment tree.
+type SegmentNode struct {
+	// Note: in a normal segment tree implementation, we would only need the sum
+	// (the other information is implicitly available as we go down the tree). But
+	// we store the other fields for the benefit of displaying them.
+	Start, End int
+	// Index of the node in Tree.Nodes.
+	Index int
+	// Sum of the values for the range [Start, End].
+	Sum  int
+	Tree *SegmentTree
+}
+
+// NewSegmentTree creates a SegmentTree with the given range.
+func NewSegmentTree(xRange int) *SegmentTree {
+	size := 1 << (bits.Len32(uint32(xRange-1)) + 1)
+	t := &SegmentTree{
+		Range: xRange,
+		Nodes: make([]SegmentNode, size),
+	}
+	t.Nodes[0] = SegmentNode{
+		Start: 1,
+		End:   xRange,
+		Tree:  t,
+		Index: 0,
+	}
+	for i := range t.Nodes {
+		if n := &t.Nodes[i]; n.End > n.Start {
+			t.Nodes[2*i+1] = SegmentNode{
+				Start: n.Start,
+				End:   (n.Start + n.End) / 2,
+				Tree:  t,
+				Index: 2*i + 1,
+			}
+			t.Nodes[2*i+2] = SegmentNode{
+				Start: (n.Start+n.End)/2 + 1,
+				End:   n.End,
+				Tree:  t,
+				Index: 2*i + 2,
+			}
+		}
+	}
+	return t
+}
+
+var _ Node = (*SegmentNode)(nil)
+
+// TreeStepsNode implements the Node interface.
+func (n *SegmentNode) TreeStepsNode() NodeInfo {
+	info := NodeInfof("n%d", n.Index)
+	info.AddPropf("range", "[%d, %d]", n.Start, n.End)
+	info.AddPropf("sum", "%d", n.Sum)
+	if n.Start < n.End {
+		info.AddChildren(
+			&n.Tree.Nodes[2*n.Index+1],
+			&n.Tree.Nodes[2*n.Index+2],
+		)
+	}
+	return info
+}
+
+// Root returns the root node of the segment tree.
+func (t *SegmentTree) Root() *SegmentNode {
+	return &t.Nodes[0]
+}
+
+// Add delta to the value for x.
+func (t *SegmentTree) Add(x int, delta int) {
+	t.add(0, x, delta)
+}
+
+func (t *SegmentTree) add(nodeIdx int, x int, delta int) {
+	n := &t.Nodes[nodeIdx]
+	if x < n.Start || n.End < x {
+		return
+	}
+	op := StartOpf(n, "add(%d, %d)", x, delta)
+	if n.Start < n.End {
+		t.add(2*nodeIdx+1, x, delta)
+		t.add(2*nodeIdx+2, x, delta)
+	}
+	n.Sum += delta
+	NodeUpdated(n, "sum updated")
+	op.Finishf("done")
+}
+
+// Sum returns the sum of the values for x1 through x2.
+func (t *SegmentTree) Sum(x1, x2 int) int {
+	return t.sum(0, x1, x2)
+}
+
+func (t *SegmentTree) sum(nodeIdx int, x1, x2 int) (result int) {
+	n := &t.Nodes[nodeIdx]
+	if x2 < n.Start || n.End < x1 {
+		return
+	}
+	if IsRecording(n) {
+		op := StartOpf(n, "sum(%d, %d)", x1, x2)
+		defer func() {
+			op.Finishf("= %d", result)
+		}()
+	}
+	if x1 <= n.Start && n.End <= x2 {
+		return n.Sum
+	}
+	return t.sum(2*nodeIdx+1, x1, x2) + t.sum(2*nodeIdx+2, x1, x2)
+}
+
+func TestSegmentTree(t *testing.T) {
+	var tree *SegmentTree
+	datadriven.RunTest(t, "testdata/segment_tree", func(t *testing.T, td *datadriven.TestData) string {
+		var r *Recording
+		switch td.Cmd {
+		case "init":
+			var xRange int
+			td.ScanArgs(t, "range", &xRange)
+			tree = NewSegmentTree(xRange)
+			return TreeToString(tree.Root())
+
+		case "add":
+			var x, delta int
+			td.ScanArgs(t, "x", &x)
+			td.ScanArgs(t, "delta", &delta)
+			r = StartRecording(tree.Root(), "Segment Tree add")
+			tree.Add(x, delta)
+
+		case "sum":
+			var x1, x2 int
+			td.ScanArgs(t, "x1", &x1)
+			td.ScanArgs(t, "x2", &x2)
+			r = StartRecording(tree.Root(), "Segment Tree sum")
+			tree.Sum(x1, x2)
+
+		default:
+			td.Fatalf(t, "unknown command %q", td.Cmd)
+		}
+		if r != nil {
+			steps := r.Finish()
+			if td.HasArg("url") {
+				url := steps.URL()
+				return url.String()
+			}
+			return steps.String()
+		}
+		return ""
+	})
+}