Segment Tree

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(log n)	O(log n)	O(log n)	O(log n)

Definition

Short

Segment Tree is a data structure that allows efficient range queries on an array. It's built by recursively dividing the array into smaller segments and storing the results of operations on those segments.

Simplified

Segment Tree is like a librarian for data. It organizes data into segments for quick searches and updates, similar to how a librarian sorts books into sections for easy access. However, once the Segment Tree is built, it can't be modified. It's a tool for efficient data management and retrieval.

Detailed

Segment Tree, or statistic tree, is a static binary tree data structure used for storing interval information. It enables queries to determine which stored segments contain a given point. The tree's root represents an entire array, with its children representing the array's halves. This pattern continues down the tree.

The tree is built from the bottom up, with each node's value being the "minimum" (or another function) of its children's values. This process takes O(n log n) time. For range queries, each node divides the query into 2 sub-queries for each child. if a query encompasses a node's entire subarray, the precomputed node value can be used.

Practice

Practice

Aspect	Pseudo Code
Init	constructor(input_array, operation, operation_fallback): input_array = input_array operation = operation operation_fallback = operation_fallback segment_tree = init_segment_tree(input_array) build_segment_tree() init_segment_tree(input_array): input_array_length = length(input_array) if is_power_of_two(input_array_length): segment_tree_array_length = (2 * input_array_length) - 1 else: current_power = floor(log2(input_array_length)) next_power = current_power + 1 next_powerOfTwoNumber = 2^next_power segment_tree_array_length = (2 * next_powerOfTwoNumber) - 1 return Array(segment_tree_array_length) is_power_of_two(number): if number < 1: return False divided_number = number While divided_number ≠ 1: if divided_number % 2 ≠ 0: return False divided_number /= 2 return True build_segment_tree(): left_index = 0 right_index = input_array.length - 1 position = 0 build_tree_recursively(left_index, right_index, position) build_tree_recursively(left_input_index, right_input_index, position): if left_input_index = right_input_index: segment_tree[position] = input_array[left_input_index] return middle_index = floor((left_input_index + right_input_index) / 2) build_tree_recursively(left_input_index, middle_index, get_left_child_index(position)) build_tree_recursively(middle_index + 1, right_input_index, get_right_child_index(position)) segment_tree[position] = operation( segment_tree[get_left_child_index(position)], segment_tree[get_right_child_index(position)] ) get_left_child_index(parentIndex): return (2 * parentIndex) + 1 get_right_child_index(parentIndex): return (2 * parentIndex) + 2
Range Query	range_query(query_left_index, query_right_index): left_index = 0 right_index = input_array.length - 1 position = 0 return range_query_helper(query_left_index, query_right_index, left_index, right_index, position) range_query_helper(query_left_index, query_right_index, left_index, right_index, position): if query_left_index ≤ left_index and query_right_index ≥ right_index: return segment_tree[position] if query_left_index > right_index or query_right_index < left_index: return operation_fallback middle_index = floor((left_index + right_index) / 2) left_operation_result = range_queryRecursive( query_left_index, query_right_index, left_index, middle_index, get_left_child_index(position) ) right_operation_result = range_queryRecursive( query_left_index, query_right_index, middle_index + 1, right_index, get_right_child_index(position) ) return operation(left_operation_result, right_operation_result) get_left_child_index(parentIndex): return (2 * parentIndex) + 1 get_right_child_index(parentIndex): return (2 * parentIndex) + 2

Solution

package main

import (
	"math"
)

type SegmentTree struct {
	InputArray       []interface{}
	Operation        func(interface{}, interface{}) interface{}
	OperationFallback interface{}
	SegmentTree      []interface{}
}

func NewSegmentTree(inputArray []interface{}, operation func(interface{}, interface{}) interface{}, operationFallback interface{}) *SegmentTree {
	segmentTree := &SegmentTree{
		InputArray:       inputArray,
		Operation:        operation,
		OperationFallback: operationFallback,
		SegmentTree:      make([]interface{}, 0),
	}

	segmentTree.initSegmentTree(inputArray)
	segmentTree.buildSegmentTree()

	return segmentTree
}

func (st *SegmentTree) initSegmentTree(inputArray []interface{}) {
	inputArrayLength := len(inputArray)
	var segmentTreeArrayLength int

	if st.isPowerOfTwo(inputArrayLength) {
		segmentTreeArrayLength = (2 * inputArrayLength) - 1
	} else {
		currentPower := int(math.Log2(float64(inputArrayLength)))
		nextPower := currentPower + 1
		nextPowerOfTwoNumber := int(math.Pow(2, float64(nextPower)))
		segmentTreeArrayLength = (2 * nextPowerOfTwoNumber) - 1
	}

	st.SegmentTree = make([]interface{}, segmentTreeArrayLength)
	for i := range st.SegmentTree {
		st.SegmentTree[i] = st.OperationFallback
	}
}

func (st *SegmentTree) isPowerOfTwo(number int) bool {
	if number < 1 {
		return false
	}

	dividedNumber := number
	for dividedNumber != 1 {
		if dividedNumber%2 != 0 {
			return false
		}
		dividedNumber /= 2
	}

	return true
}

func (st *SegmentTree) buildSegmentTree() {
	leftIndex := 0
	rightIndex := len(st.InputArray) - 1
	position := 0
	st.buildTreeRecursively(leftIndex, rightIndex, position)
}

func (st *SegmentTree) buildTreeRecursively(leftInputIndex, rightInputIndex, position int) {
	if leftInputIndex == rightInputIndex {
		st.SegmentTree[position] = st.InputArray[leftInputIndex]
		return
	}

	middleIndex := (leftInputIndex + rightInputIndex) / 2
	st.buildTreeRecursively(leftInputIndex, middleIndex, st.getLeftChildIndex(position))
	st.buildTreeRecursively(middleIndex+1, rightInputIndex, st.getRightChildIndex(position))

	st.SegmentTree[position] = st.Operation(st.SegmentTree[st.getLeftChildIndex(position)], st.SegmentTree[st.getRightChildIndex(position)])
}

func (st *SegmentTree) RangeQuery(queryLeftIndex, queryRightIndex int) interface{} {
	leftIndex := 0
	rightIndex := len(st.InputArray) - 1
	position := 0

	return st.rangeQueryHelper(queryLeftIndex, queryRightIndex, leftIndex, rightIndex, position)
}

func (st *SegmentTree) rangeQueryHelper(queryLeftIndex, queryRightIndex, leftIndex, rightIndex, position int) interface{} {
	if queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex {
		return st.SegmentTree[position]
	}

	if queryLeftIndex > rightIndex || queryRightIndex < leftIndex {
		return st.OperationFallback
	}

	middleIndex := (leftIndex + rightIndex) / 2
	leftOperationResult := st.rangeQueryHelper(queryLeftIndex, queryRightIndex, leftIndex, middleIndex, st.getLeftChildIndex(position))
	rightOperationResult := st.rangeQueryHelper(queryLeftIndex, queryRightIndex, middleIndex+1, rightIndex, st.getRightChildIndex(position))

	return st.Operation(leftOperationResult, rightOperationResult)
}

func (st *SegmentTree) getLeftChildIndex(parentIndex int) int {
	return (2 * parentIndex) + 1
}

func (st *SegmentTree) getRightChildIndex(parentIndex int) int {
	return (2 * parentIndex) + 2
}

import java.util.ArrayList;
import java.util.List;

public class SegmentTree<T> {

  private final BinaryOperation<T> operation;
  private final T operationFallback;
  private List<T> inputArray;
  private List<T> segmentTree;

  public SegmentTree(List<T> inputArray, BinaryOperation<T> operation, T operationFallback) {
    this.inputArray = inputArray;
    this.operation = operation;
    this.operationFallback = operationFallback;
    this.segmentTree = initSegmentTree(inputArray);
    buildSegmentTree();
  }

  private List<T> initSegmentTree(List<T> inputArray) {
    int inputArrayLength = inputArray.size();
    int segmentTreeArrayLength;

    if (isPowerOfTwo(inputArrayLength)) {
      segmentTreeArrayLength = (2 * inputArrayLength) - 1;
    } else {
      int currentPower = (int) (Math.log(inputArrayLength) / Math.log(2));
      int nextPower = currentPower + 1;
      int nextPowerOfTwoNumber = (int) Math.pow(2, nextPower);
      segmentTreeArrayLength = (2 * nextPowerOfTwoNumber) - 1;
    }

    List<T> segmentTree = new ArrayList<>(segmentTreeArrayLength);
    for (int i = 0; i < segmentTreeArrayLength; i++) {
      segmentTree.add(operationFallback);
    }

    return segmentTree;
  }

  private boolean isPowerOfTwo(int number) {
    if (number < 1) {
      return false;
    }

    int dividedNumber = number;
    while (dividedNumber != 1) {
      if (dividedNumber % 2 != 0) {
        return false;
      }
      dividedNumber /= 2;
    }

    return true;
  }

  private void buildSegmentTree() {
    int leftIndex = 0;
    int rightIndex = inputArray.size() - 1;
    int position = 0;
    buildTreeRecursively(leftIndex, rightIndex, position);
  }

  private void buildTreeRecursively(int leftInputIndex, int rightInputIndex, int position) {
    if (leftInputIndex == rightInputIndex) {
      segmentTree.set(position, inputArray.get(leftInputIndex));
      return;
    }

    int middleIndex = (leftInputIndex + rightInputIndex) / 2;
    buildTreeRecursively(leftInputIndex, middleIndex, getLeftChildIndex(position));
    buildTreeRecursively(middleIndex + 1, rightInputIndex, getRightChildIndex(position));

    segmentTree.set(position, operation.apply(segmentTree.get(getLeftChildIndex(position)),
        segmentTree.get(getRightChildIndex(position))));
  }

  public T rangeQuery(int queryLeftIndex, int queryRightIndex) {
    int leftIndex = 0;
    int rightIndex = inputArray.size() - 1;
    int position = 0;
    return rangeQueryHelper(queryLeftIndex, queryRightIndex, leftIndex, rightIndex, position);
  }

  private T rangeQueryHelper(int queryLeftIndex, int queryRightIndex, int leftIndex, int rightIndex, int position) {
    if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
      return segmentTree.get(position);
    }

    if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
      return operationFallback;
    }

    int middleIndex = (leftIndex + rightIndex) / 2;
    T leftOperationResult = rangeQueryHelper(queryLeftIndex, queryRightIndex, leftIndex, middleIndex, getLeftChildIndex(position));
    T rightOperationResult = rangeQueryHelper(queryLeftIndex, queryRightIndex, middleIndex + 1, rightIndex, getRightChildIndex(position));

    return operation.apply(leftOperationResult, rightOperationResult);
  }

  private int getLeftChildIndex(int parentIndex) {
    return (2 * parentIndex) + 1;
  }

  private int getRightChildIndex(int parentIndex) {
    return (2 * parentIndex) + 2;
  }

  public interface BinaryOperation<T> {

    T apply(T a, T b);
  }
}

class SegmentTree {
  constructor(inputArray, operation, operationFallback) {
    this.inputArray = inputArray;
    this.operation = operation;
    this.operationFallback = operationFallback;

    this.segmentTree = this.initSegmentTree(this.inputArray);

    this.buildSegmentTree();
  }

  initSegmentTree(inputArray) {
    let segmentTreeArrayLength;
    const inputArrayLength = inputArray.length;

    if (this.isPowerOfTwo(inputArrayLength)) {
      segmentTreeArrayLength = 2 * inputArrayLength - 1;
    } else {
      const currentPower = Math.floor(Math.log2(inputArrayLength));
      const nextPower = currentPower + 1;
      const nextPowerOfTwoNumber = 2 ** nextPower;
      segmentTreeArrayLength = 2 * nextPowerOfTwoNumber - 1;
    }

    return new Array(segmentTreeArrayLength).fill(null);
  }

  buildSegmentTree() {
    const leftIndex = 0;
    const rightIndex = this.inputArray.length - 1;
    const position = 0;
    this.buildTreeRecursively(leftIndex, rightIndex, position);
  }

  buildTreeRecursively(leftInputIndex, rightInputIndex, position) {
    if (leftInputIndex === rightInputIndex) {
      this.segmentTree[position] = this.inputArray[leftInputIndex];
      return;
    }

    const middleIndex = Math.floor((leftInputIndex + rightInputIndex) / 2);
    this.buildTreeRecursively(
      leftInputIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    );
    this.buildTreeRecursively(
      middleIndex + 1,
      rightInputIndex,
      this.getRightChildIndex(position),
    );

    this.segmentTree[position] = this.operation(
      this.segmentTree[this.getLeftChildIndex(position)],
      this.segmentTree[this.getRightChildIndex(position)],
    );
  }

  rangeQuery(queryLeftIndex, queryRightIndex) {
    const leftIndex = 0;
    const rightIndex = this.inputArray.length - 1;
    const position = 0;

    return this.rangeQueryRecursive(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      rightIndex,
      position,
    );
  }

  rangeQueryRecursive(
    queryLeftIndex,
    queryRightIndex,
    leftIndex,
    rightIndex,
    position,
  ) {
    if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
      return this.segmentTree[position];
    }

    if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
      return this.operationFallback;
    }

    const middleIndex = Math.floor((leftIndex + rightIndex) / 2);

    const leftOperationResult = this.rangeQueryRecursive(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    );

    const rightOperationResult = this.rangeQueryRecursive(
      queryLeftIndex,
      queryRightIndex,
      middleIndex + 1,
      rightIndex,
      this.getRightChildIndex(position),
    );

    return this.operation(leftOperationResult, rightOperationResult);
  }

  getLeftChildIndex(parentIndex) {
    return 2 * parentIndex + 1;
  }

  getRightChildIndex(parentIndex) {
    return 2 * parentIndex + 2;
  }

  isPowerOfTwo(number) {
    if (number < 1) {
      return false;
    }

    let dividedNumber = number;
    while (dividedNumber !== 1) {
      if (dividedNumber % 2 !== 0) {
        return false;
      }
      dividedNumber /= 2;
    }

    return true;
  }
}

data class SegmentTree<T>(
        val inputArray: List<T>,
        val operation: (T, T) -> T,
        val operationFallback: T
) {

    var segmentTree: MutableList<T> = initSegmentTree(inputArray)

    init {
        buildSegmentTree()
    }

    private fun initSegmentTree(inputArray: List<T>): MutableList<T> {
        val inputArrayLength = inputArray.size

        val segmentTreeArrayLength = if (isPowerOfTwo(inputArrayLength)) {
            (2 * inputArrayLength) - 1
        } else {
            val currentPower = (Math.log(inputArrayLength.toDouble()) / Math.log(2.0)).toInt()
            val nextPower = currentPower + 1
            val nextPowerOfTwoNumber = 2.0.pow(nextPower.toDouble()).toInt()
            (2 * nextPowerOfTwoNumber) - 1
        }

        return MutableList(segmentTreeArrayLength) { _ -> operationFallback }
    }

    private fun isPowerOfTwo(number: Int): Boolean {
        if (number < 1) {
            return false
        }

        var dividedNumber = number
        while (dividedNumber != 1) {
            if (dividedNumber % 2 != 0) {
                return false
            }
            dividedNumber /= 2
        }

        return true
    }

    private fun buildSegmentTree() {
        val leftIndex = 0
        val rightIndex = inputArray.size - 1
        val position = 0
        buildTreeRecursively(leftIndex, rightIndex, position)
    }

    private fun buildTreeRecursively(leftInputIndex: Int, rightInputIndex: Int, position: Int) {
        if (leftInputIndex == rightInputIndex) {
            segmentTree[position] = inputArray[leftInputIndex]
            return
        }

        val middleIndex = (leftInputIndex + rightInputIndex) / 2
        buildTreeRecursively(leftInputIndex, middleIndex, getLeftChildIndex(position))
        buildTreeRecursively(middleIndex + 1, rightInputIndex, getRightChildIndex(position))

        segmentTree[position] = operation(segmentTree[getLeftChildIndex(position)], segmentTree[getRightChildIndex(position)])
    }

    fun rangeQuery(queryLeftIndex: Int, queryRightIndex: Int): T {
        val leftIndex = 0
        val rightIndex = inputArray.size - 1
        val position = 0

        return rangeQueryHelper(queryLeftIndex, queryRightIndex, leftIndex, rightIndex, position)
    }

    private fun rangeQueryHelper(queryLeftIndex: Int, queryRightIndex: Int, leftIndex: Int, rightIndex: Int, position: Int): T {
        if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
            return segmentTree[position]
        }

        if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
            return operationFallback
        }

        val middleIndex = (leftIndex + rightIndex) / 2
        val leftOperationResult = rangeQueryHelper(queryLeftIndex, queryRightIndex, leftIndex, middleIndex, getLeftChildIndex(position))
        val rightOperationResult = rangeQueryHelper(queryLeftIndex, queryRightIndex, middleIndex + 1, rightIndex, getRightChildIndex(position))

        return operation(leftOperationResult, rightOperationResult)
    }

    private fun getLeftChildIndex(parentIndex: Int): Int {
        return (2 * parentIndex) + 1
    }

    private fun getRightChildIndex(parentIndex: Int): Int {
        return (2 * parentIndex) + 2
    }
}

class SegmentTree:
    def __init__(self, input_array, operation, operation_fallback):
        self.input_array = input_array
        self.operation = operation
        self.operation_fallback = operation_fallback
        self.segment_tree = self.init_segment_tree(self.input_array)
        self.build_segment_tree()

    def init_segment_tree(self, input_array):
        input_array_length = len(input_array)

        if self.is_power_of_two(input_array_length):
            segment_tree_array_length = 2 * input_array_length - 1
        else:
            current_power = int(input_array_length.bit_length() - 1)
            next_power = current_power + 1
            next_power_of_two_number = 2 ** next_power
            segment_tree_array_length = 2 * next_power_of_two_number - 1

        return [None] * segment_tree_array_length

    def build_segment_tree(self):
        left_index = 0
        right_index = len(self.input_array) - 1
        position = 0
        self.build_tree_recursively(left_index, right_index, position)

    def build_tree_recursively(self, left_input_index, right_input_index, position):
        if left_input_index == right_input_index:
            self.segment_tree[position] = self.input_array[left_input_index]
            return

        middle_index = (left_input_index + right_input_index) // 2
        self.build_tree_recursively(
            left_input_index,
            middle_index,
            self.get_left_child_index(position),
        )
        self.build_tree_recursively(
            middle_index + 1,
            right_input_index,
            self.get_right_child_index(position),
        )

        self.segment_tree[position] = self.operation(
            self.segment_tree[self.get_left_child_index(position)],
            self.segment_tree[self.get_right_child_index(position)],
        )

    def range_query(self, query_left_index, query_right_index):
        left_index = 0
        right_index = len(self.input_array) - 1
        position = 0

        return self.range_query_recursive(
            query_left_index,
            query_right_index,
            left_index,
            right_index,
            position,
        )

    def range_query_recursive(
        self, query_left_index, query_right_index, left_index, right_index, position
    ):
        if query_left_index <= left_index and query_right_index >= right_index:
            return self.segment_tree[position]

        if query_left_index > right_index or query_right_index < left_index:
            return self.operation_fallback

        middle_index = (left_index + right_index) // 2

        left_operation_result = self.range_query_recursive(
            query_left_index,
            query_right_index,
            left_index,
            middle_index,
            self.get_left_child_index(position),
        )

        right_operation_result = self.range_query_recursive(
            query_left_index,
            query_right_index,
            middle_index + 1,
            right_index,
            self.get_right_child_index(position),
        )

        return self.operation(left_operation_result, right_operation_result)

    def get_left_child_index(self, parent_index):
        return 2 * parent_index + 1

    def get_right_child_index(self, parent_index):
        return 2 * parent_index + 2

    def is_power_of_two(self, number):
        if number < 1:
            return False

        divided_number = number
        while divided_number != 1:
            if divided_number % 2 != 0:
                return False
            divided_number //= 2

        return True

struct SegmentTree<T> {
    input_array: Vec<T>,
    operation: fn(T, T) -> T,
    operation_fallback: T,
    segment_tree: Vec<T>,
}

impl<T> SegmentTree<T> {
    fn new(input_array: Vec<T>, operation: fn(T, T) -> T, operation_fallback: T) -> Self {
        let mut segment_tree = Self::init_segment_tree(&input_array);

        Self {
            input_array,
            operation,
            operation_fallback,
            segment_tree,
        }
    }

    fn init_segment_tree(input_array: &Vec<T>) -> Vec<T> {
        let input_array_length = input_array.len();
        let mut segment_tree_array_length;

        if Self::is_power_of_two(input_array_length) {
            segment_tree_array_length = 2 * input_array_length - 1;
        } else {
            let current_power = (input_array_length as f64).log2().floor() as usize;
            let next_power = current_power + 1;
            let next_power_of_two_number = 2usize.pow(next_power as u32);
            segment_tree_array_length = 2 * next_power_of_two_number - 1;
        }

        vec![None; segment_tree_array_length]
    }

    fn is_power_of_two(number: usize) -> bool {
        if number < 1 {
            return false;
        }

        let mut divided_number = number;
        while divided_number != 1 {
            if divided_number % 2 != 0 {
                return false;
            }
            divided_number /= 2;
        }

        true
    }

    fn build_segment_tree(&mut self) {
        let left_index = 0;
        let right_index = self.input_array.len() - 1;
        let position = 0;
        self.build_tree_recursively(left_index, right_index, position);
    }

    fn build_tree_recursively(&mut self, left_input_index: usize, right_input_index: usize, position: usize) {
        if left_input_index == right_input_index {
            self.segment_tree[position] = self.input_array[left_input_index].clone();
            return;
        }

        let middle_index = (left_input_index + right_input_index) / 2;
        self.build_tree_recursively(
            left_input_index,
            middle_index,
            self.get_left_child_index(position),
        );
        self.build_tree_recursively(
            middle_index + 1,
            right_input_index,
            self.get_right_child_index(position),
        );

        self.segment_tree[position] = (self.operation)(
            self.segment_tree[self.get_left_child_index(position)].clone(),
            self.segment_tree[self.get_right_child_index(position)].clone(),
        );
    }

    fn range_query(&self, query_left_index: usize, query_right_index: usize) -> T {
        let left_index = 0;
        let right_index = self.input_array.len() - 1;
        let position = 0;

        self.range_query_recursive(
            query_left_index,
            query_right_index,
            left_index,
            right_index,
            position,
        )
    }

    fn range_query_recursive(
        &self,
        query_left_index: usize,
        query_right_index: usize,
        left_index: usize,
        right_index: usize,
        position: usize,
    ) -> T {
        if query_left_index <= left_index && query_right_index >= right_index {
            return self.segment_tree[position].clone();
        }

        if query_left_index > right_index || query_right_index < left_index {
            return self.operation_fallback.clone();
        }

        let middle_index = (left_index + right_index) / 2;

        let left_operation_result = self.range_query_recursive(
            query_left_index,
            query_right_index,
            left_index,
            middle_index,
            self.get_left_child_index(position),
        );

        let right_operation_result = self.range_query_recursive(
            query_left_index,
            query_right_index,
            middle_index + 1,
            right_index,
            self.get_right_child_index(position),
        );

        (self.operation)(left_operation_result, right_operation_result)
    }

    fn get_left_child_index(&self, parent_index: usize) -> usize {
        2 * parent_index + 1
    }

    fn get_right_child_index(&self, parent_index: usize) -> usize {
        2 * parent_index + 2
    }
}

class SegmentTree<T> {
  inputArray: T[];
  operation: (a: T, b: T) => T;
  operationFallback: T;
  segmentTree: (T | null)[];

  constructor(
    inputArray: T[],
    operation: (a: T, b: T) => T,
    operationFallback: T,
  ) {
    this.inputArray = inputArray;
    this.operation = operation;
    this.operationFallback = operationFallback;

    this.segmentTree = this.initSegmentTree(this.inputArray);

    this.buildSegmentTree();
  }

  rangeQuery(queryLeftIndex: number, queryRightIndex: number): T {
    const leftIndex = 0;
    const rightIndex = this.inputArray.length - 1;
    const position = 0;

    return this.rangeQueryRecursive(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      rightIndex,
      position,
    );
  }

  private initSegmentTree(inputArray: T[]): (T | null)[] {
    let segmentTreeArrayLength: number;
    const inputArrayLength = inputArray.length;

    if (this.isPowerOfTwo(inputArrayLength)) {
      segmentTreeArrayLength = 2 * inputArrayLength - 1;
    } else {
      const currentPower = Math.floor(Math.log2(inputArrayLength));
      const nextPower = currentPower + 1;
      const nextPowerOfTwoNumber = 2 ** nextPower;
      segmentTreeArrayLength = 2 * nextPowerOfTwoNumber - 1;
    }

    return new Array(segmentTreeArrayLength).fill(null);
  }

  private buildSegmentTree(): void {
    const leftIndex = 0;
    const rightIndex = this.inputArray.length - 1;
    const position = 0;
    this.buildTreeRecursively(leftIndex, rightIndex, position);
  }

  private buildTreeRecursively(
    leftInputIndex: number,
    rightInputIndex: number,
    position: number,
  ): void {
    if (leftInputIndex === rightInputIndex) {
      this.segmentTree[position] = this.inputArray[leftInputIndex];
      return;
    }

    const middleIndex = Math.floor((leftInputIndex + rightInputIndex) / 2);
    this.buildTreeRecursively(
      leftInputIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    );
    this.buildTreeRecursively(
      middleIndex + 1,
      rightInputIndex,
      this.getRightChildIndex(position),
    );

    this.segmentTree[position] = this.operation(
      this.segmentTree[this.getLeftChildIndex(position)],
      this.segmentTree[this.getRightChildIndex(position)],
    );
  }

  private rangeQueryRecursive(
    queryLeftIndex: number,
    queryRightIndex: number,
    leftIndex: number,
    rightIndex: number,
    position: number,
  ): T {
    if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
      return this.segmentTree[position] as T;
    }

    if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
      return this.operationFallback;
    }

    const middleIndex = Math.floor((leftIndex + rightIndex) / 2);

    const leftOperationResult = this.rangeQueryRecursive(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    );

    const rightOperationResult = this.rangeQueryRecursive(
      queryLeftIndex,
      queryRightIndex,
      middleIndex + 1,
      rightIndex,
      this.getRightChildIndex(position),
    );

    return this.operation(leftOperationResult, rightOperationResult);
  }

  private getLeftChildIndex(parentIndex: number): number {
    return 2 * parentIndex + 1;
  }

  private getRightChildIndex(parentIndex: number): number {
    return 2 * parentIndex + 2;
  }

  private isPowerOfTwo(number: number): boolean {
    if (number < 1) {
      return false;
    }

    let dividedNumber = number;
    while (dividedNumber !== 1) {
      if (dividedNumber % 2 !== 0) {
        return false;
      }
      dividedNumber /= 2;
    }

    return true;
  }
}