Я столкнулся с интересной проблемой, основанной на древовидной структуре данных.
Нам дано дерево, которое имеет N узлов, с 1≤N≤10 5 .
Время начинается со секунды 1 и продолжается q секунд.
В каждую секунду значение каждого внутреннего узла передается всем его дочерним узлам. Это происходит со всеми узлами, кроме конечных узлов.
Иногда в данный момент времени p (секунд) нас просят вернуть текущее значение узла x * 1021. *.
Существует такой подход O (logN) * 1026 *: просто найдите p th предка данного узла x и выведите его значение.
Более сложная версия той же проблемы
Иногда в определенный момент времени p (секунд) нас просят вернуть текущее значение узла *Говорят, что 1040 * x , или обновляют значение узла x до y .
Как решить эту проблему для q запросов (секунд), где 1≤q≤10 5 .
Пример
Ввод
N = 5, q = 8
Края дерева: -
4 3
3 1
5 2
1 2
Значения узлов с 1 по 5: -
1 10 4 9 4
Запросы: -
- 1 st секунда: -
Add(1,6). Добавьте значение 6 к узлу 1. - 2 nd секунда: - Каково текущее значение узла 3?
(?,3) - 3 rd секунда: -
Add(3,5) - 4 th секунда: -
(?,3) - 5 th секунда: -
Add(2,2) - 6 th секунда: -
Add(5,10) - 7 th секунда: -
(?,5) - 8 th секунда: -
(?,4)
Ожидаемый результат
Пояснение
- 1 st секунда: 6,1,1,13,14 (значения всех узлов)
- 2 и секунды: 0,6,6,14,15
- 3 числа секунды:0,0,5,20,21
- 4 th секунда: 0,0,0,25,21
- 5 th секунда:0,2,0,25,21
- 6 th секунда: 0,0,0,25,33
- 7 th секунда:0,0,0,25,33
- 8 th секунда: 0,0,0,25,33
Как эффективно отвечать на запросы?