Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

datastructures
segment tree

What is a segment tree?

Educative Answers Team

A segment tree is a data structure used to store information about array segments and answer segment queries efficiently. There are two main operations performed on a segment tree:

  1. range(i, j): gives the sum of the array elements starting at index i and ending at index j.

  2. update(i, val): updates the value at index i to the val in the original array and updates the segment tree accordingly.

Both range(i, j) and update(i, val) take log(n)log(n) time, where n is the number of elements in the segment tree.

Construction

A segment tree is usually represented in an array. The following illustration shows an array and its corresponding segment tree (represented as a tree and array).

The input array
1 of 3

Update

The following illustration explains how a segment tree is updated. The segment tree is represented as a tree for better ​understanding:

The input array. update(2, 2) i.e update the element at index 2 to 2
1 of 6

Range query

The following illustration goes over how range(i, j) works:

The input array. The task is to find range(0, 3) i.e, ti find the sum of the first four array elements,
1 of 3

RELATED TAGS

datastructures
segment tree
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring