72
правки
Изменения
→Построение дерева
TreeBuild(a, 2*i+1, tm, tr);
t[i] = t[2*i] + t[2*i+1];
Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении снизу алгоритм поднимается от листьев к корню, как в [[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве | динамике по поддереву]], а при построении сверху спускается от корня к листьям, как указано в реализации. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.
==Ссылки==
