Описание тега segment-tree
A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time.
A segment tree is a balanced tree where each node corresponds to an interval. The leaves correspond to the atomic intervals according to left to right order. An internal node u corresponds to the union of the intervals corresponding to the leaves of the subtree rooted at u.
A segment tree for a set of n intervals can be constructed in O(nlogn) time.
A d-dimensional segment tree for a set of n axis-aligned rectangular boxes in R d can be built in O(n(logn)^ d) time and takes O(n(logn)^ d) space.