Segment Tree

Range QueriesO(log n)

A binary tree for efficiently answering range sum queries and point updates.

Array values (1–99)

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Edit the array values, then click Build.

Click "Build" to construct the segment tree.

queried path

update path

leaf

internal

Left index

Right index

Index

New value

build(arr)

O(n)

Build tree from array

query(l, r)

O(log n)

Range sum query

update(i, v)

O(log n)

Point update

Space

O(n)

4n nodes in tree