What is the time complexity of segment tree?

Worst case O(log n) query and update. Space complexity is O(4n). Any range splits into O(log n) canonical nodes.

Segment tree

hard

Every node owns a range; any query decomposes into at most 2 log n precomputed pieces. Three cases - no overlap, total overlap, partial - and only the third recurses.

Worst O(log n) query and updateSpace O(4n)

Loading the segment tree engine…

Where to go next

Fenwick tree (BIT)

hard

Prefix sums in one array, driven by the lowest set bit.

Prefix sums

easy

Precompute once, answer every range query in O(1).

AVL tree

hard

Four rotation cases that refuse to let the tree lean.