Структура данных для нахождения линий между двумя высотами - PullRequest
Новая
       6

Структура данных для нахождения линий между двумя высотами

0 голосов
/ 17 мая 2018

Я реализую простое приложение, в котором у меня хранится несколько значений lineHeights, например: 

lineHeights = [2, 4, 5, 7, 2, 4, 5, /* ... */]

Теперь, учитывая две высоты, a и b Мне нужно найти диапазон строкмежду a и b

Например, если высота равна [2, 2, 4, 5, 2], то диапазон строк между 3 и 7 будет [1, 2] как строки 12 содержатся в указанном диапазоне высот.

Наивной реализацией было бы сохранение строк в виде массива и перемещение по массиву, чтобы увидеть, какие линии находятся между заданными высотами, как показанов следующем псевдокоде (который я не тестировал, но надеюсь, вы понимаете, что я показываю): 

get_line_range_between_heights (lines start_height end_height)
  index = 0
  height = 0
  while true
    height = height + lines[index]
    if height >= start_height
      break
    index = index + 1
  result_ranges = [index]
  while true
    height = height + lines[index]
    if height >= end_height
      break
    index = index + 1
  push index into result_ranges
  return result_ranges

Однако простая реализация обходится дорого - при вставке и удалении высотбыстро, запрос становится операцией O(n), где n - количество строк

Поэтому мой вопрос - существует ли какая-то структура данных (например, что-то вроде бинарного дерева поиска), которая в идеалебудет иметь операции вставки, удаления и поиска (для строк между двумя высотами) в O(n) или лучше, что специализировано для такого рода проблем (в идеале с реализацией или ссылкой на одну из них)?

...