Segment Tree

Range queries and point updates with lazy propagation.

8 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Segment Tree Structure

Segment tree is a binary tree where each node represents an interval. Root = [0, n-1]. Leaves = single elements. Internal node = merge of children. Stored in array of size 4n. Index 1 = root, left child = 2*i, right = 2*i+1.

Gosegment-tree-for-range-sum.go

52 linesLn 1, Col 1Go

Build: O(n). Query: O(log n) - visit at most 2 nodes per level. Point update: O(log n) - update leaf, recalc parents.

Lazy Propagation

For range updates (e.g., add val to [L,R]). Store pending updates in lazy array. Push down only when needed (before querying children or updating further).

Golazy-propagation-for-range-add.go

35 linesLn 1, Col 1Go

When entering node, apply pending lazy. If fully covered, update node and mark children lazy. Else recurse. Query also needs to apply lazy first.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.