Трудно понять рекурсию для построения дерева сегментов

Question

Предположим, есть массив с n = 5

int [] arr = {1,2,3,4,5};

и

int [] segmentTree = new int[n*4];

Вот код для построения этого сегмента Tree

buildSegmentTree(a , 1 , 0 , n-1);

void buildSegmentTree(int [] a  , int vertex , int leftLimit , int rightLimit)
{    
     if(leftLimit == rightLimit)
     segmentTree[vertex] = a[leftLimit];
     else
     {
          int mid = (leftLimit + rightLimit)/2;
          //Builds the left part of the Segment Tree
          buildSegmentTree(a , vertex * 2 , leftLimit , mid);
          //Builds the right part of the Segment Tree
          buildSegmentTree(a , vertex*2 + 1 , mid+1 , rightLimit);
          segmentTree[vertex] = segmentTree[vertex*2] + segmentTree[vertex*2 + 1];
     }
}

Когда я печатаю значения дерева сегментов, это вывод, который я получаю

0 15 6 9 3 3 4 5 1 2 0 0 0 0 0 0 0 0 0 0

Я понимаючто означают эти значения (например, 15 - это сумма 6 и 9), но я не понимаю, как они сохраняются и как выполняются вызовы.

Answer 1

Вы можете легко понять это, построив дерево на бумаге.
Имейте в виду:
Если у узла есть интервал (0, n-1), то у левого потомка есть (0,mid) и правый дочерний элемент (mid + 1, n-1).

В соответствии с данным массивом arr , для интервала (0,4) принимается значениеэто самый первый узел, который у вас есть. Теперь, найдя середину этого интервала, мы сделали двух дочерних: один слева (0,2), а другой (3,4). Теперь это выглядит так:
(0, 4)
/ \
(0, 2) (3, 4)
Теперь аналогичным образом разделяем левого и правого потомков, пока мы не получим leftLimit = rightLimit , поэтому итоговое дерево выглядит так:
(0, 4)
/ \
(0, 2) (3, 4)
/ \ / \
(0, 1) (2, 2) (3, 3) (4, 4)
/ \
(0, 0) (1, 1)

Сумма 0 и1-й элемент массива , т. Е. 1 и 2 сохраняются в узле с интервалом (0,1), сумма (0,1) и (2,2) сохраняется в(0,2) и так далее.

Таким образом дерево будет построено с корневым элементом, содержащим сумму всего массива arr . Для более подробной информации перейдите по ссылке
https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/
Надеюсь, что это будет иметь смысл и будет полезно:)