.. _Segment_Tree:

Segment Tree
==========================

A Segment Tree is a data structure that allows answering **range queries** over an array effectively, while still being flexible enough to allow modifying the array.


**Features of Segment trees**:

1. Leaf Nodes are the elements of the input array. This is like `tournament tree` described at :numref:`Tournament_Tree`.

2. Each internal node represents some merging of the leaf nodes. The merging may be different for different problems. If we want to query minimum value of a range, merging is minimum of leaves under a node.


.. _subarray_minimum_query:

Subarray Minimum Query
^^^^^^^^^^^^^^^^^^^^^^^^^^^^


There are many ways to implement a segement tree. The following is an example to build a minimum segement tree using `vector` as the underlying data strucutre.

.. literalinclude:: segment_tree_min.h
  :language: c++
  :linenos:
  :lines: 7-45
  :emphasize-lines: 7-9,16-20,26-32

In the above implementation, we deliberately don't use the first item in the underlying vector. So the node at array[index] has its children at array[index*2] and array[index*2+1]. The node at array[index] has its parent at array[index/2]. [#]_

If the original array is {5,2,3,1,4}. First we copy all the array to the second part of the underlying vector. Then we populate the inner nodes.

.. figure:: img/flat_min_stree.png
  :name: flat_min_stree
  :align: center

  Segment Tree Indexing Scheme

Finally we will get a segment tree as a **full binary tree** [#]_.

.. figure:: img/segment_tree_min.png
  :name: segment_tree_min_1
  :align: center
  :width: 280

  Construct Segment Tree


.. code:: None

             [2]
          /       \
        [2]      [4]
        /   \     /  \
  data [2]  [3]  [4] [5]

  original index: [0][1][2][3]
  original array: [2][3][4][5]
  index: [x][1][2][3][4][5][6][7]   (tree index)
  value: [x][2][2][4][2][3][4][5]   (tree)

  input 0,3 => 4, 7

                   [2]
                 /  /
             [2]---/---
            /     /    \
         [2]   [2]     [5]   
         /    /   \   /  \
  data [2]  [3]  [4] [5] [6]



To make the tree easier to see, we can adjust it like:

.. figure:: img/segment_tree_min.svg
  :name: segment_tree_min_2
  :align: center
  :width: 280

  Segment Tree As Full Binary Tree

The tricky part is the `query` function, where we need to check if the upper level's parent node has the left-most or right-most node as a child. If not, we need to add the left-most or right-most node into the calculation.

.. rubric:: Footnotes

.. [#] A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. Heap is complete binary tree. None of them are not necessarily perfect binary tree.

.. [#] The indexing scheme is different from what described for 0-index-based heap. For heap,  the item at array[index] has its children at array[index*2+1] and array[index*2+2]. The node at array[index] has its parent at array[(index-1)/2].



Buddy System Bitmap
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. literalinclude:: segment_tree_bitmap.h
  :language: c++
  :linenos:
  :lines: 51-100
  :emphasize-lines: 10-21,26-42

.. only:: html

  - `heap tree indexing scheme <https://stackoverflow.com/questions/22900388/why-in-a-heap-implemented-by-array-the-index-0-is-left-unused>`_