Implemented Segment Tree Data Structure

[Ramy-Badr-Ahmed]

Contents:

• SegmentTreeNode Class: Represents individual nodes in the Segment Tree with attributes start, end, value, left, and right. Where:

  • start and end: Define the range of the array segment covered by this node.
    • value: Stores the aggregated result (e.g., sum, min, max) for this segment, determined by the callback function passed during construction. Defaults to arithmetic sum if no callback is provided.

  • left and right: Pointers to the left and right child nodes, allowing traversal through the tree.

    The SegmentTreeNode class encapsulates the ranges and results, linking to left and right child nodes.

• SegmentTree Class: Implements the core functionalities of a Segment Tree.

  • buildTree: Constructs the tree from the input array, using a callback function to define custom operations (e.g., sum, max).
  • update: Updates the value at a specified index, adjusting the tree accordingly with the updateTree method.
  • rangeUpdate: Updates values across a specified range, propagating changes through the tree with the rangeUpdateTree method.
  • query: Retrieves an aggregated result (e.g., sum, max) from a specified array range using the queryTree method for traversal.
  • getCurrentArray: Returns the current array representation of the segment tree.
  • getRoot: Returns the root node of the segment tree.
  • serialize: Converts the segment tree into a JSON string.

  • deserialize: Restores it from the serialized format.

    The class supports arbitrary operations (e.g., sum, min, max) using callback functions, or falls back to a sum-based tree if no callback is provided.

• Unit Tests:

  SegmentTreeTest.php: Contains PHPUnit tests to validate the correct behavior of segment tree building, querying, updating, performing range updates, and serialization and deserialization to ensure persistence of tree structure.

Time Complexity

A time complexity of O(log n) for both query and update operations, where n is the size of the input array. The build operation takes O(n log n) in total.

GitHub Actions

All tests and workflows (in my forked repository) have passed:

• PHPCS

• DIRECTORY.md

• build

---

Reference

The Algorithm Design Manual, Latest edition

[Ramy-Badr-Ahmed]

Thank you for the addition!

Thanks for the review and merge 🙂