Learn
Segment Tree
A Segment Tree is a tree data structure for performing range queries and point updates in time. It's also known as a statistic tree.
You build a binary tree where each node stores aggregate information (like sum, min, or max) for a range of the array.
function build(arr, tree, node, start, end):
if start == end:
tree[node] = arr[start]
return
mid = (start + end) / 2
build(arr, tree, 2*node, start, mid)
build(arr, tree, 2*node+1, mid+1, end)
tree[node] = tree[2*node] + tree[2*node+1]
function query(tree, node, start, end, L, R):
if R < start or end < L:
return 0
if L <= start and end <= R:
return tree[node]
mid = (start + end) / 2
return query(tree, 2*node, start, mid, L, R) +
query(tree, 2*node+1, mid+1, end, L, R)
function update(tree, node, start, end, idx, val):
if start == end:
tree[node] = val
return
mid = (start + end) / 2
if idx <= mid:
update(tree, 2*node, start, mid, idx, val)
else:
update(tree, 2*node+1, mid+1, end, idx, val)
tree[node] = tree[2*node] + tree[2*node+1]
Array representation: You use an array of size to store the tree. Node 's children are at and .