Nano Hash - криптовалюты, майнинг, программирование

Запросы подмассива

Поэтому я пытался решить эту проблему программирования.

Дан массив чисел и несколько запросов. Каждый запрос дает вам три числа a,b,c и просит вас ответить на сумму всех элементов от индекса a до индекса b (включая оба), которые меньше или равны c.

Например:

Данный массив: {2,4,6,1,5,1,6,4,5,4}

Необходимо ответить на 3 вопроса:

2 4 4 -> ответ=5 т.е. {4+1}

1 5 3 -> ответ=3 т.е. {2+1}

4 5 1 -> ответ=1

каждое значение в массиве меньше 10 ^ 5, длина массива и количество запросов могут варьироваться до 10 ^ 5

Вот что я сделал. Я использовал алгоритм Мо (разложение квадратного корня) для сортировки запросов и создал двоичное индексированное дерево для хранения совокупной суммы элементов, меньших, чем все значения от 1 до 10 ^ 5, и сделал обновление, перейдя от запросы к запросам. С этим алгоритмом общая сложность моего решения составляет O (q * sqrt (N) * log (N)), но это недостаточно быстро. Я искал лучший алгоритм. Я думаю, что разложение запросов на квадратный корень не сработает. Есть ли лучший алгоритм для решения этой проблемы?

Мне было интересно, может ли какая-то структура данных решить эту проблему, о которой я не знаю?

optimization algorithm data-structures tree
06.06.2017

  • Вы имеете в виду, что a, b, c - это индексы? И используете ли вы индексацию с нуля? 07.06.2017
  • @Bahrom a и b - это индексы, основанные на «1», c - это число. 07.06.2017

Ответы:


1

Вы можете разложить его наоборот. А именно, построить дерево полумассивов (это пространство ????(n log n)). Отсортируйте каждый подмассив и постройте для него совокупный массив сумм. Теперь ваши запросы равны ????(log2 n) каждый (log n для идентификации подмассивов и еще один log n чтобы найти кумулятивную сумму в каждом подмассиве).

Например, если ваш исходный массив

            5,10,2,7,16,4,8,9

ты сначала построишь это дерево

            5,10,2,7,16,4,8,9
              /         \
      5,10,2,7           16,4,8,9
      /      \           /      \
    5,10     2,7      16,4      8,9
    / \      / \      / \       / \
   5   10   2   7   16   4     8   9

затем рассортируйте их все

           2,4,5,7,8,9,10,16
              /         \
      2,5,7,10           4,8,9,16
      /      \           /      \
    5,10     2,7      4,16      8,9
    / \      / \      / \       / \
   5   10   2   7   16   4     8   9

Теперь, если вы хотите ответить на запрос, скажем, (1,6,8) (индексы основаны на 0), вы разложите интервал (1,6) на двоичные подынтервалы (1) (2,3) (4,5) (6) (их не более 2 log n), затем найдите ответ для каждого отдельно (0 для (1)={10}, 9 для (2,3)={2,7} , 4 для (4,5)={16,4}, 8 для (6)={8}) и суммируем их.

Начальное построение дерева может быть выполнено в ????(n log n), если вы отсортируете пары (значение, индекс) один раз, а затем просто пройдете по отсортированному массиву log n раз (один раз для каждого уровня дерева) и скопируйте значения в соответствующие узлы.

07.06.2017
  • Что касается реализации, вы можете определить рекурсивную функцию в дереве, которая (1) просто возвращает сумму текущего узла, если он полностью содержится в интервале, (2) возвращает результат функции на левой или правой дочерней сумме если интервал находится только с левой или правой стороны, (3) возвращает сумму вызова функции как для левого, так и для правого дочерних элементов, если интервал находится с обеих сторон, т. е. проходит за середину. Это кажется проще, чем пытаться полностью разбить интервал в начале. Это похоже на O(log n) на запрос. 07.06.2017
  • Можете ли вы уточнить, как найти фактическую сумму элементов, меньшую или равную c (в O (log n))? Один из способов сделать это — сохранить кумулятивную сумму для каждого узла, а затем выполнить двоичный поиск в этом узле, чтобы найти подходящую сумму. 11.06.2017

    • 2

    1. сортировать запросы по c

    2. отсортировать значения массива в порядке неубывания

    3. поддерживать (битовое дерево сегментов) для хранения суммы диапазона

    4. перед ответом на текущий запрос обновить индекс всех элементов массива, значение которых ‹= c

    5. ответить на проблему суммы запроса диапазона.

    Временная сложность: (n+q)*log(n), пространственная сложность: O(n)

    27.12.2020
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..