Trees
Building your tree…
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Trees
Building your tree…
Divide-and-conquer tree that answers range-sum queries and point updates in O(log n). Each internal node stores the aggregate of its segment.
Array (index 0-based):
Node index shown below each circle. tree[1] = sum of entire array.
def build(node, start, end):
if start == end:
tree[node] = arr[start]; return
mid = (start + end) // 2
build(2*node, start, mid)
build(2*node+1, mid+1, end)
tree[node] = tree[2*node] + tree[2*node+1]
def query(node, start, end, l, r):
if r < start or end < l:
return 0 # outside range
if l <= start and end <= r:
return tree[node] # fully inside
mid = (start + end) // 2
return (query(2*node, start, mid, l, r)
+ query(2*node+1, mid+1, end, l, r))What is the time complexity of a range-sum query on a segment tree?
1/3