Несмотря на другие ответы, можно использовать деревья Фенвика для запросов о минимальном диапазоне для любого диапазона. Я разместил здесь подробное объяснение:
Как адаптировать дерево Фенвика к диапазону ответов минимум запросов
Короче говоря, вам нужно поддерживать
- массив, представляющий реальные значения для узлов [1, N]
- дерево Фенвика с 0 в качестве корня, где родителем любого узла i является
i-(i&-i)
- дерево Фенвика с N + 1 в качестве корня, где родителем любого узла i является
i+(i&-i)
Чтобы запросить любой диапазон в O (log n)
Query(int a, int b) {
int val = infinity // always holds the known min value for our range
// Start traversing the first tree, BIT1, from the beginning of range, a
int i = a
while (parentOf(i, BIT1) <= b) {
val = min(val, BIT2[i]) // Note: traversing BIT1, yet looking up values in BIT2
i = parentOf(i, BIT1)
}
// Start traversing the second tree, BIT2, from the end of range, b
i = b
while (parentOf(i, BIT2) >= a) {
val = min(val, BIT1[i]) // Note: traversing BIT2, yet looking up values in BIT1
i = parentOf(i, BIT2)
}
val = min(val, REAL[i])
return val
}
Чтобы обновить любое значение в амортизированном O (log n), вам необходимо обновить реальный массив и оба дерева. Обновление отдельного дерева:
while (node <= n+1) {
if (v > tree[node]) {
if (oldValue == tree[node]) {
v = min(v, real[node])
for-each child {
v = min(v, tree[child])
}
} else break
}
if (v == tree[node]) break
tree[node] = v
node = parentOf(node, tree)
}
person
Atte Juvonen
schedule
05.01.2016
