Segment Tree

Medium

Segment Tree

A data structure that groups array partial sums into a tree, handling range-sum queries and point updates in O(log n).

📊 Complexity

Type	Value
Best	O(log n)
Average	O(log n)
Worst	O(log n)
Space	O(n)

🏷️ Tags

Data StructureTreeRange Sum

📖 Introduction

A segment tree is a binary tree that splits an array into "segments" and stores each segment's sum in a node. The root covers the whole range, each leaf a single element.

1/31

🌳Range Sums, Fast

Summing a range [l..r] each time is O(n). If we precompute partial sums in a tree, both queries and updates run in O(log n).

🔒

Segment Tree

Medium

Segment Tree

A data structure that groups array partial sums into a tree, handling range-sum queries and point updates in O(log n).

📊 Complexity

Type	Value
Best	O(log n)
Average	O(log n)
Worst	O(log n)
Space	O(n)

🏷️ Tags

Data StructureTreeRange Sum

📖 Introduction

A segment tree is a binary tree that splits an array into "segments" and stores each segment's sum in a node. The root covers the whole range, each leaf a single element.

1/31

🌳Range Sums, Fast

Summing a range [l..r] each time is O(n). If we precompute partial sums in a tree, both queries and updates run in O(log n).

🔒

🌳Range Sums, Fast

Segment Tree

Definition

Key Characteristics

Time Complexity

🌳Range Sums, Fast

Segment Tree

Definition

Key Characteristics

Time Complexity