Introduction
Do you ever feel overwhelmed trying to find the best solution for handling large-scale search queries? Then a segment tree may be just what you are looking for! A segment tree allows data structures and algorithms to efficiently find answers to efficiently process range queries, such as finding the minimum or maximum value in an interval of numbers. In this article, we will look at how a segment tree works and how it can help you solve complex problems more quickly and accurately.
What is a segment tree
The segment tree is an efficient and useful data structure in computer programming and data analysis. Essentially, a segment tree is a tree data structure used to process different range queries over an array or another linear data structure. It breaks down an array or range into smaller segments, each containing a subset of the original data, creating a tree-like hierarchy. This segmented approach enables the tree to perform particular operations, such as finding the maximum element in a range or updating a value in the array, more quickly and efficiently than other algorithms. Overall, the segment tree is an excellent tool for handling a wide range of complex data queries and should be a valuable addition to any programmer's toolbox.
Properties of segment tree
- Binary Tree Structure: A segment tree is a complete binary tree, meaning that all levels except possibly the last level is completely filled, and all nodes are left-aligned.
- Leaf Nodes: The leaf nodes of a segment tree represent individual elements of the input array. Each leaf node contains the value of a single element.
- Non-Leaf Nodes: The non-leaf nodes of the segment tree represent segments or ranges of elements from the input array. Each non-leaf node contains information derived from its child nodes. For example, a node representing the range [l, r] would store the sum, minimum, maximum, or any other aggregate value of the elements in that range.
- Range Division: The range [l, r] of the input array is divided into two halves: [l, mid] and [mid+1, r], where mid is the midpoint of the range. These halves correspond to the left and right child of a node in the segment tree.
- Recursion: The construction and queries of a segment tree are typically implemented using recursive algorithms. The tree is built by recursively dividing the input range and building the tree bottom-up.
- Querying: Segment trees enable efficient range queries. To query a range [ql, qr], the tree is traversed in a top-down manner, and the relevant segments that overlap with the query range are processed.
- Updating: Segment trees also allow efficient updates to individual elements. To update an element at index i, the tree is traversed in a bottom-up manner, and the relevant segments that contain the element are updated accordingly.
- Time Complexity: The construction of a segment tree requires O(n) time, where n is the number of elements in the input array. Both querying and updating operations can be performed in O(log n) time.
Advantages of segment tree
- Efficient Range Queries: Segment trees excel at performing range queries on dynamic arrays or sequences. They allow you to answer queries about a specific range of elements in logarithmic time complexity (O(log n)), regardless of the size of the array. This makes them highly efficient for problems involving searching, counting, summing, finding minimum or maximum values, and other similar operations over ranges.
- Dynamic Updates: Segment trees can efficiently handle updates to the elements of an array or sequence. Whether it's modifying a single element or updating a range of values, segment trees can perform these updates in logarithmic time complexity. This ability to handle dynamic updates makes them suitable for scenarios where the array elements change frequently.
- Versatility: Segment trees are flexible and adaptable. They can be used for various types of data, such as integers, floating-point numbers, or even non-numeric values, as long as you define appropriate operations for the data type. This versatility allows segment trees to be applied in a wide range of problems, including computational geometry, statistics, and data analysis.
- Space Efficiency: Although segment trees require additional memory to store the tree structure, they typically provide a space-efficient solution. The space complexity of a segment tree is O(n), where n represents the number of elements in the array. This efficiency arises from the recursive nature of segment trees, where memory is shared among overlapping segments.
- Easy to Implement: Segment trees have a relatively straightforward implementation compared to other complex data structures like balanced search trees or advanced graph algorithms. The basic operations of constructing a segment tree, querying, and updating are easy to understand and implement. Once you grasp the concept, you can quickly apply segment trees to various problems.
- Range Decomposition: Segment trees naturally decompose an array or sequence into smaller segments, allowing for efficient recursive processing. This property makes them useful in divide-and-conquer algorithms, where problems are divided into smaller subproblems, solved recursively, and then combined to obtain the final result.
Disadvantages of segment tree
- Space Complexity: Segment trees require additional space to store the tree structure, which can be a disadvantage in scenarios where memory usage is a concern. The space complexity of a segment tree is O(n), where n is the number of elements in the input array.
- Construction Time: Building a segment tree can take a significant amount of time, especially when the input array is large. The construction process involves recursively dividing the array into smaller segments and performing operations to build the tree. The time complexity of constructing a segment tree is O(n), where n is the number of elements in the input array.
- Updates and Modifications: Although segment trees excel at querying and computing aggregate functions over a range of elements efficiently, updating or modifying individual elements can be more time-consuming. When an element in the input array changes, the corresponding segment tree needs to be updated to reflect the modification, which can require traversing multiple tree nodes. The time complexity for updating an element in a segment tree is O(log n), where n is the number of elements in the input array.
- Static Structure: Segment trees are designed to work with static or semi-static arrays. If the input array frequently changes its size or elements, rebuilding the segment tree from scratch can be inefficient. In such cases, other data structures like Fenwick trees or balanced binary search trees may be more suitable.
- Complex Implementation: Implementing a segment tree can be challenging compared to simpler data structures. The recursive nature of segment trees and the need for efficient indexing can make the code more intricate and error-prone. Understanding and implementing various operations, such as range queries and updates, require a good grasp of tree algorithms
Operations of Segment Tree
A segment tree is a versatile data structure that efficiently handles various range queries on an array. It allows for quick updates and queries on contiguous subarrays, making it useful in a wide range of applications. The main operations of a segment tree include construction, update, and query. Let's discuss each operation in detail:
1) Construction:
- To build a segment tree, you start with an array of elements.
- The segment tree is represented as a binary tree, where each node corresponds to a range of indices in the array.
- Initially, the root of the segment tree represents the entire array (range [0, n-1], where n is the size of the array).
- Recursively, the tree is divided into two halves until each leaf node represents a single element of the array.
- The internal nodes of the segment tree represent ranges that are the union of their child nodes' ranges.
def build_segment_tree(segment_tree, input_array, low, high, pos):
if low == high:
segment_tree[pos] = input_array[low]
return
mid = low + (high - low) // 2
build_segment_tree(segment_tree, input_array, low, mid, 2 * pos + 1)
build_segment_tree(segment_tree, input_array, mid + 1, high, 2 * pos + 2)
segment_tree[pos] = segment_tree[2 * pos + 1] + segment_tree[2 * pos + 2]
def construct_segment_tree(input_array):
n = len(input_array)
tree_size = 2 * n - 1
segment_tree = [0] * tree_size
build_segment_tree(segment_tree, input_array, 0, n - 1, 0)
return segment_tree
def print_segment_tree(segment_tree):
print("Segment Tree:", end=" ")
for i in segment_tree:
print(i, end=" ")
print()
if __name__ == "__main__":
input_array = [1, 3, 5, 7, 9, 11]
segment_tree = construct_segment_tree(input_array)
print_segment_tree(segment_tree)
import java.util.Arrays;
class Main {
// Function to build the segment tree
static void buildSegmentTree(int[] segmentTree, int[] inputArray, int low, int high, int pos) {
if (low == high) {
segmentTree[pos] = inputArray[low];
return;
}
int mid = low + (high - low) / 2;
buildSegmentTree(segmentTree, inputArray, low, mid, 2 * pos + 1);
buildSegmentTree(segmentTree, inputArray, mid + 1, high, 2 * pos + 2);
segmentTree[pos] = segmentTree[2 * pos + 1] + segmentTree[2 * pos + 2];
}
// Function to initialize and build the segment tree
static int[] constructSegmentTree(int[] inputArray) {
int n = inputArray.length;
int treeSize = 2 * n - 1;
int[] segmentTree = new int[treeSize];
Arrays.fill(segmentTree, 0);
buildSegmentTree(segmentTree, inputArray, 0, n - 1, 0);
return segmentTree;
}
// Function to print the segment tree
static void printSegmentTree(int[] segmentTree) {
System.out.print("Segment Tree: ");
for (int i = 0; i < segmentTree.length; ++i) {
System.out.print(segmentTree[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] inputArray = {1, 3, 5, 7, 9, 11};
int[] segmentTree = constructSegmentTree(inputArray);
printSegmentTree(segmentTree);
}
}
#include <iostream>
#include <vector>
using namespace std;
// Function to build the segment tree
void buildSegmentTree(vector<int>& segmentTree, const vector<int>& inputArray, int low, int high, int pos) {
if (low == high) {
segmentTree[pos] = inputArray[low];
return;
}
int mid = low + (high - low) / 2;
buildSegmentTree(segmentTree, inputArray, low, mid, 2 * pos + 1);
buildSegmentTree(segmentTree, inputArray, mid + 1, high, 2 * pos + 2);
segmentTree[pos] = segmentTree[2 * pos + 1] + segmentTree[2 * pos + 2];
}
// Function to initialize and build the segment tree
vector<int> constructSegmentTree(const vector<int>& inputArray) {
int n = inputArray.size();
int treeSize = 2 * n - 1;
vector<int> segmentTree(treeSize, 0);
buildSegmentTree(segmentTree, inputArray, 0, n - 1, 0);
return segmentTree;
}
// Function to print the segment tree
void printSegmentTree(const vector<int>& segmentTree) {
cout << "Segment Tree: ";
for (int i = 0; i < segmentTree.size(); ++i) {
cout << segmentTree[i] << " ";
}
cout << endl;
}
int main() {
vector<int> inputArray = {1, 3, 5, 7, 9, 11};
vector<int> segmentTree = constructSegmentTree(inputArray);
printSegmentTree(segmentTree);
return 0;
}Output
Segment Tree: 36 9 27 4 5 16 11 1 3 0 0 7 9 0 0
2) Update
To update in segment tree an element in the original array, you traverse the segment tree starting from the root.
At each node, you compare the range it represents with the target index.
If the range matches the target index, you update the node with the new value.
Otherwise, you recursively descend into the appropriate child node that covers the target index.
This process continues until you reach the leaf node representing the target index.
def update(tree, index, start, end, updateIndex, value):
if start == end:
# Leaf node, update the value
tree[index] = value
else:
mid = (start + end) // 2
# If the update index is in the left subtree
if updateIndex <= mid:
update(tree, 2 * index + 1, start, mid, updateIndex, value)
else:
# If the update index is in the right subtree
update(tree, 2 * index + 2, mid + 1, end, updateIndex, value)
# Recalculate the parent node value after updating the child nodes
tree[index] = tree[2 * index + 1] + tree[2 * index + 2]
def query(tree, index, start, end, queryStart, queryEnd):
if queryStart > end or queryEnd < start:
# The range is completely outside the current node's range
return 0
elif queryStart <= start and queryEnd >= end:
# The range is completely inside the current node's range
return tree[index]
else:
mid = (start + end) // 2
# Recursively query the left and right subtrees
leftSum = query(tree, 2 * index + 1, start, mid, queryStart, queryEnd)
rightSum = query(tree, 2 * index + 2, mid + 1, end, queryStart, queryEnd)
return leftSum + rightSum
arr = [1, 3, 5, 7, 9, 11]
# Build the segment tree
n = len(arr)
tree = [0] * (4 * n)
for i in range(n):
update(tree, 0, 0, n - 1, i, arr[i])
# Print the segment tree
print("Segment Tree:", end=" ")
for i in tree:
print(i, end=" ")
print()
# Perform an update operation
updateIndex = 2 # Index to update
newValue = 6 # New value to assign
update(tree, 0, 0, n - 1, updateIndex, newValue)
# Print the updated segment tree
print("Updated Segment Tree:", end=" ")
for i in tree:
print(i, end=" ")
print()
# Perform a range sum query
queryStart = 1 # Query start index
queryEnd = 4 # Query end index
sum = query(tree, 0, 0, n - 1, queryStart, queryEnd)
print(f"Sum from index {queryStart} to {queryEnd}: {sum}")
import java.util.Arrays;
class Main {
// Function to update a value in the segment tree
static void update(int[] tree, int index, int start, int end, int updateIndex, int value) {
if (start == end) {
// Leaf node, update the value
tree[index] = value;
} else {
int mid = (start + end) / 2;
// If the update index is in the left subtree
if (updateIndex <= mid) {
update(tree, 2 * index + 1, start, mid, updateIndex, value);
} else {
// If the update index is in the right subtree
update(tree, 2 * index + 2, mid + 1, end, updateIndex, value);
}
// Recalculate the parent node value after updating the child nodes
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
}
// Function to perform a range sum query in the segment tree
static int query(int[] tree, int index, int start, int end, int queryStart, int queryEnd) {
if (queryStart > end || queryEnd < start) {
// The range is completely outside the current node's range
return 0;
} else if (queryStart <= start && queryEnd >= end) {
// The range is completely inside the current node's range
return tree[index];
} else {
int mid = (start + end) / 2;
// Recursively query the left and right subtrees
int leftSum = query(tree, 2 * index + 1, start, mid, queryStart, queryEnd);
int rightSum = query(tree, 2 * index + 2, mid + 1, end, queryStart, queryEnd);
return leftSum + rightSum;
}
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
// Build the segment tree
int n = arr.length;
int[] tree = new int[4 * n];
Arrays.fill(tree, 0);
for (int i = 0; i < n; ++i) {
update(tree, 0, 0, n - 1, i, arr[i]);
}
// Print the segment tree
System.out.print("Segment Tree: ");
for (int i = 0; i < tree.length; ++i) {
System.out.print(tree[i] + " ");
}
System.out.println();
// Perform an update operation
int updateIndex = 2; // Index to update
int newValue = 6; // New value to assign
update(tree, 0, 0, n - 1, updateIndex, newValue);
// Print the updated segment tree
System.out.print("Updated Segment Tree: ");
for (int i = 0; i < tree.length; ++i) {
System.out.print(tree[i] + " ");
}
System.out.println();
// Perform a range sum query
int queryStart = 1; // Query start index
int queryEnd = 4; // Query end index
int sum = query(tree, 0, 0, n - 1, queryStart, queryEnd);
System.out.println("Sum from index " + queryStart + " to " + queryEnd + ": " + sum);
}
}
#include <iostream>
#include <vector>
using namespace std;
// Function to update a value in the segment tree
void update(vector<int>& tree, int index, int start, int end, int updateIndex, int value) {
if (start == end) {
// Leaf node, update the value
tree[index] = value;
} else {
int mid = (start + end) / 2;
// If the update index is in the left subtree
if (updateIndex <= mid) {
update(tree, 2 * index + 1, start, mid, updateIndex, value);
} else {
// If the update index is in the right subtree
update(tree, 2 * index + 2, mid + 1, end, updateIndex, value);
}
// Recalculate the parent node value after updating the child nodes
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
}
// Function to perform a range sum query in the segment tree
int query(vector<int>& tree, int index, int start, int end, int queryStart, int queryEnd) {
if (queryStart > end || queryEnd < start) {
// The range is completely outside the current node's range
return 0;
} else if (queryStart <= start && queryEnd >= end) {
// The range is completely inside the current node's range
return tree[index];
} else {
int mid = (start + end) / 2;
// Recursively query the left and right subtrees
int leftSum = query(tree, 2 * index + 1, start, mid, queryStart, queryEnd);
int rightSum = query(tree, 2 * index + 2, mid + 1, end, queryStart, queryEnd);
return leftSum + rightSum;
}
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
// Build the segment tree
int n = arr.size();
vector<int> tree(4 * n);
for (int i = 0; i < n; ++i) {
update(tree, 0, 0, n - 1, i, arr[i]);
}
// Print the segment tree
cout << "Segment Tree: ";
for (int i = 0; i < tree.size(); ++i) {
cout << tree[i] << " ";
}
cout << endl;
// Perform an update operation
int updateIndex = 2; // Index to update
int newValue = 6; // New value to assign
update(tree, 0, 0, n - 1, updateIndex, newValue);
// Print the updated segment tree
cout << "Updated Segment Tree: ";
for (int i = 0; i < tree.size(); ++i) {
cout << tree[i] << " ";
}
cout << endl;
// Perform a range sum query
int queryStart = 1; // Query start index
int queryEnd = 4; // Query end index
int sum = query(tree, 0, 0, n - 1, queryStart, queryEnd);
cout << "Sum from index " << queryStart << " to " << queryEnd << ": " << sum << endl;
return 0;
}
Output
Segment Tree: 36 9 27 4 5 16 11 1 3 0 0 0 7 9 0 0
Updated Segment Tree: 36 9 27 4 5 16 11 1 3 0 0 0 7 6 0 0
Sum from index 1 to 4: 24
3) Query
- A segment tree query involves finding some information about a specific range in the original array.
- To perform a query, you start at the root of the segment tree.
- At each node, you compare the node's range with the target range.
- If the ranges are disjoint (i.e., no overlap), you return an appropriate default value (e.g., 0 or infinity) since the range is not present in the current node.
- If the node's range is entirely contained within the target range, you return the value stored at that node.
- Otherwise, you recursively descend into the left and right child nodes, considering only the parts of the target range that overlap with the child nodes' ranges.
- Finally, you combine the results obtained from the child nodes to obtain the desired query result.
import math
# Function to build the segment tree
def buildSegmentTree(arr, segmentTree, low, high, pos):
if low == high:
segmentTree[pos] = arr[low]
return
mid = low + (high - low) // 2
buildSegmentTree(arr, segmentTree, low, mid, 2 * pos + 1)
buildSegmentTree(arr, segmentTree, mid + 1, high, 2 * pos + 2)
segmentTree[pos] = segmentTree[2 * pos + 1] + segmentTree[2 * pos + 2]
# Function to perform the query operation
def query(segmentTree, qlow, qhigh, low, high, pos):
if qlow <= low and qhigh >= high:
return segmentTree[pos]
if qlow > high or qhigh < low:
return 0
mid = low + (high - low) // 2
return query(segmentTree, qlow, qhigh, low, mid, 2 * pos + 1) + query(segmentTree, qlow, qhigh, mid + 1, high, 2 * pos + 2)
arr = [1, 3, 5, 7, 9, 11]
n = len(arr)
# Calculate the size of the segment tree
treeSize = 2 * int(math.pow(2, math.ceil(math.log2(n)))) - 1
# Create the segment tree
segmentTree = [0] * treeSize
# Build the segment tree
buildSegmentTree(arr, segmentTree, 0, n - 1, 0)
# Perform queries
qlow, qhigh = map(int, input("Enter the range of the query (0-based indexing): ").split())
sum = query(segmentTree, qlow, qhigh, 0, n - 1, 0)
print("Sum of elements in the given range:", sum)
import java.util.Scanner;
public class SegmentTreeQuery {
// Function to build the segment tree
static void buildSegmentTree(int[] arr, int[] segmentTree, int low, int high, int pos) {
if (low == high) {
segmentTree[pos] = arr[low];
return;
}
int mid = low + (high - low) / 2;
buildSegmentTree(arr, segmentTree, low, mid, 2 * pos + 1);
buildSegmentTree(arr, segmentTree, mid + 1, high, 2 * pos + 2);
segmentTree[pos] = segmentTree[2 * pos + 1] + segmentTree[2 * pos + 2];
}
// Function to perform the query operation
static int query(int[] segmentTree, int qlow, int qhigh, int low, int high, int pos) {
if (qlow <= low && qhigh >= high) {
return segmentTree[pos];
}
if (qlow > high || qhigh < low) {
return 0;
}
int mid = low + (high - low) / 2;
return query(segmentTree, qlow, qhigh, low, mid, 2 * pos + 1) +
query(segmentTree, qlow, qhigh, mid + 1, high, 2 * pos + 2);
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int n = arr.length;
// Calculate the size of the segment tree
int treeSize = 2 * (int) Math.pow(2, Math.ceil(Math.log(n) / Math.log(2))) - 1;
// Create the segment tree
int[] segmentTree = new int[treeSize];
// Build the segment tree
buildSegmentTree(arr, segmentTree, 0, n - 1, 0);
// Perform queries
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the range of the query (0-based indexing): ");
int qlow = scanner.nextInt();
int qhigh = scanner.nextInt();
int sum = query(segmentTree, qlow, qhigh, 0, n - 1, 0);
System.out.println("Sum of elements in the given range: " + sum);
}
}
#include <iostream>
#include <vector>
using namespace std;
// Function to build the segment tree
void buildSegmentTree(vector<int>& arr, vector<int>& segmentTree, int low, int high, int pos) {
if (low == high) {
segmentTree[pos] = arr[low];
return;
}
int mid = low + (high - low) / 2;
buildSegmentTree(arr, segmentTree, low, mid, 2 * pos + 1);
buildSegmentTree(arr, segmentTree, mid + 1, high, 2 * pos + 2);
segmentTree[pos] = segmentTree[2 * pos + 1] + segmentTree[2 * pos + 2];
}
// Function to perform the query operation
int query(vector<int>& segmentTree, int qlow, int qhigh, int low, int high, int pos) {
if (qlow <= low && qhigh >= high) {
return segmentTree[pos];
}
if (qlow > high || qhigh < low) {
return 0;
}
int mid = low + (high - low) / 2;
return query(segmentTree, qlow, qhigh, low, mid, 2 * pos + 1) +
query(segmentTree, qlow, qhigh, mid + 1, high, 2 * pos + 2);
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
int n = arr.size();
// Calculate the size of the segment tree
int treeSize = 2 * pow(2, ceil(log2(n))) - 1;
// Create the segment tree
vector<int> segmentTree(treeSize);
// Build the segment tree
buildSegmentTree(arr, segmentTree, 0, n - 1, 0);
// Perform queries
int qlow, qhigh;
cout << "Enter the range of the query (0-based indexing): ";
cin >> qlow >> qhigh;
int sum = query(segmentTree, qlow, qhigh, 0, n - 1, 0);
cout << "Sum of elements in the given range: " << sum << endl;
return 0;
}Output
Enter the range of the query (0-based indexing): 1 4
Sum of elements in the given range: 24
The complexity of segment tree
The complexity of a segment tree depends on the specific operations you perform on it and the implementation details. Let's analyze the complexity of the common operations on a segment tree.
1. Construction:
- Time complexity: O(n), where n is the number of elements in the input array. During construction, each element of the input array needs to be processed and inserted into the tree.
- Space complexity: O(n), as the segment tree requires an array of size 4n to store the tree nodes.
2. Query:
- Time complexity: O(log n), where n is the number of elements in the input array. The query operation traverses the segment tree from the root to the desired range, which takes O(log n) time.
- Space complexity: O(1).
3. Update:
- Time complexity: O(log n), where n is the number of elements in the input array. The update operation modifies the segment tree nodes along the path from the root to the updated element, which takes O(log n) time.
- Space complexity: O(1).
Summary
In conclusion, segment tree is a powerful data structure that offers an efficient way to solve range queries and update operations. Its structure makes it possible to perform these operations in a fraction of the time that other data structures would require. All in all, it has become a valuable tool for applications such as range queries, updates, and operations on intervals. Implementing segment trees can greatly improve speed and accuracy when searching for data or performing calculations over intervals of any size. With so many applications available in the computer science field, this data structure is sure to be an invaluable asset when dealing with large datasets. Therefore, if you’re looking for an efficient way to tackle range queries and update operations on your dataset, consider using a segment tree today!
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
