✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-209

Segment Trees

A Segment Tree is a binary tree-based data structure used to answer range queries and perform updates efficiently on an array.

Explanation

Overview

A Segment Tree divides an array into smaller intervals. Each node represents a segment of the array and stores information about that segment, such as its sum, minimum, maximum, or greatest common divisor.

How it works

The root represents the entire array.; Each internal node divides its segment into two smaller segments.; The process continues until each leaf represents one array element.; Each node stores an aggregate value calculated from its children.; A range query combines information from the relevant nodes.; An update modifies the affected leaf and recalculates values along its path to the root.

Key concepts

Binary tree; Array intervals; Tree nodes; Range queries; Point updates; Aggregate functions

Time complexity

operation: Build; complexity: O(n); operation: Range Query; complexity: O(log n); operation: Point Update; complexity: O(log n)

Space complexity

O(n), commonly implemented with an array of approximately 4n elements.

Example

array: 2; 4; query: Find the sum of elements from index 1 to index 4.; calculation: 4 + 1 + 7 + 3 = 15; result: 15

Applications

Competitive programming; Range sum queries; Range minimum and maximum queries; Interval-based problems; Dynamic array processing

Example or application

Array

  • 2

  • 4

  • 1

  • 7

  • 3

  • 5

Query

Find the sum of elements from index 1 to index 4.

Calculation

4 + 1 + 7 + 3 = 15

Result

15

Definition

A Segment Tree divides an array into smaller intervals. Each node represents a segment of the array and stores information about that segment, such as its sum, minimum, maximum, or greatest common divisor.

How It Works

  • The root represents the entire array.

  • Each internal node divides its segment into two smaller segments.

  • The process continues until each leaf represents one array element.

  • Each node stores an aggregate value calculated from its children.

  • A range query combines information from the relevant nodes.

  • An update modifies the affected leaf and recalculates values along its path to the root.

Supported Operations

OperationDescription

Build

Constructs the tree from the original array.

Range Query

Calculates an aggregate value over a specified interval.

Point Update

Changes one array element and updates the affected tree nodes.

Implementation

Description

A recursive implementation stores tree nodes in an array. For an input array of size n, an allocation of approximately 4n positions is commonly sufficient.

Pseudocode

  • function build(node, left, right):

  • if left == right:

  • tree[node] = array[left]

  • return

  • mid = (left + right) // 2

  • build(node * 2, left, mid)

  • build(node * 2 + 1, mid + 1, right)

  • tree[node] = tree[node * 2] + tree[node * 2 + 1]

Time Complexity

OperationComplexity

Build

O(n)

Range Query

O(log n)

Point Update

O(log n)

Space Complexity

O(n), commonly implemented with an array of approximately 4n elements.

Key Concepts

  • Binary tree

  • Array intervals

  • Tree nodes

  • Range queries

  • Point updates

  • Aggregate functions

Advantages

  • Supports efficient range queries.

  • Handles updates without rebuilding the entire structure.

  • Can support sums, minimums, maximums, and other suitable associative operations.

  • Can be extended with lazy propagation for range updates.

Limitations

  • Requires more memory than the original array.

  • Implementation is more complex than prefix sums for simple static queries.

  • Recursive implementations require careful boundary management.

Applications

  • Competitive programming

  • Range sum queries

  • Range minimum and maximum queries

  • Interval-based problems

  • Dynamic array processing

Related Topics

  • Lazy Propagation

  • Fenwick Trees

  • Sparse Tables

  • Binary Trees

  • Range Query Algorithms

Practice Questions

QuestionAnswer

What is a Segment Tree used for?

It efficiently performs range queries and updates on arrays.

What is the time complexity of a range query?

O(log n) for a standard Segment Tree.

What can a Segment Tree store?

Aggregated information such as sums, minimums, maximums, or greatest common divisors.

Learning Objectives

  • Explain the central idea and purpose of segment trees.

  • Identify the assumptions, inputs, and conditions relevant to segment trees.

  • Evaluate an application of segment trees for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures