Сумма всех чисел меньше k в диапазоне с использованием дерева сегментов - PullRequest
Новая
       43

Сумма всех чисел меньше k в диапазоне с использованием дерева сегментов

1 голос
/ 08 октября 2019

У меня есть массив A с размером элементов <= 10 ^ 6. </p>

Я хочу реализовать структуру данных, которая дает мне сумму всех элементов за вычетом k в определенном диапазоне, скажем, от l до r.

Я знаю, что это можно решитьиспользуя дерево сегментов, но не знаю, как поддерживать дерево сегментов для переменных k запросов. Пожалуйста, помогите мне с псевдокодом.

Поскольку нет обновлений, я думаю, что алгоритмы Мо также могут быть использованы.

1 Ответ

1 голос
/ 09 октября 2019

Ниже предполагается, что все элементы в вашем массиве положительные

как насчет того, чтобы не поддерживать дерево сегментов для конкретного k, а вместо этого разрешать запрос

Просто рассмотрите вашисегментное дерево.

В каждом узле Node_i вы знаете:

  • его покрывающая сумма: s_i
  • количество охватываемых элементов: n_i

Итак, два шага:

  1. Для данного запроса диапазона перейдите к соответствующему узлу Node_i.
  2. Для этого Node_i, s_i сумма двух детей. Для каждого из данных дочерних элементов Node_j с охватываемыми элементами n_j: две возможности
    • n_j*k < s_j: все элементы меньше k
    • n_j*k >= s_j: хотя бы один элемент равенбольше или равно k

Итак, в первом случае сумма ребенка уже действительна, делать больше нечего.

Во втором случае вы должныисследовать ребенка и так далее до тех пор, пока ничего больше не нужно делать

В какой-то момент (если у вас есть недопустимый элемент) вы достигнете низа дерева: этот самый узел (также элемент) плохой, ивы вернетесь к этому факту. Когда вы вернетесь к своему узлу Node_i, вы вычтете из s_i все найденные вами значения этих плохих конечных узлов.

псевдокод: 

#node is like: 
#children:[c1, c2]
#n:number of elem covered
#sum: sum of all elemens it covers
#returns the sum of the covered elements whose value is __greater__ or equal than k
def explore(node, k):
    #terminal case
    if node.n == 1:
        if node.sum >= k:
            return node.sum
        # when the range query is of size 1..., 
        # you may want to handle that elsewhere (e.g before calling explore)
        return 0
    end

    #standard case
    [c1,c2] = node.children
    totalsum = 0
    if c1.n * k < c1.sum
        #all your elems are less than k, substract nothing
        totalsum += 0 
    else
        totalsum += explore(c1, k)
    #same for c2...
    return totalsum
...