1
Я реализовал BST, содержащий в своих n узлах объект типа Point (x, y), порядок в дереве соответствует значениям X.BST search problen
мне нужно реализовать функцию, которая получает в качестве входных данных диапазона Х (х слева, X справа) и выход (РЕДАКТИРОВАТЬ): сумма координат Y в диапазоне (включительно).
Это не так сложно сделать, «пройдя» по всем узлам, проблема заключается в том, что я как-то сделал это в O (logn).
Я думал о intializing полей диапазонов и суммы Y, но почему-то это не работает с функциями вставки и удаления. любые идеи?
Я уверен, что они означали «O (log n + | right-left |)», который по-прежнему «O (log n)», но с большим количеством переменных. – Bergi
В качестве альтернативы вы можете аккумулировать сумму по всем пунктам и кэшировать ее в каждом узле, чтобы быстро найти сумму диапазона, только глядя на ее края. – Bergi