Множественность целых чисел в диапазоне

A - это массив, содержащий не более 10 целые числа.Множественность целых чисел в диапазоне

Мы должны выполнить 2 вида операций над этим массивом в сложности log (N) (где N = количество элементов в A).

Операция 1, учитывая v, я, J мы должны добавить v к A [K](я < < = к = у).

Операция 2, учитывая я & J вычислить (А [я] * A [I + 1] * A [I + 2] * .... * А [J])% М , (M является простым и будет одинаковым для всех операций).

Будет почти 10 Операции, которые предстоит выполнить.

Если это невозможно в журнале (N), то какова максимальная сложность операций?

источник

2013-08-21 Bidhan Roy

Для операции 1, вы действительно имеете в виду 'add v' или' multiply by v'? Для 'multiply by v' мое решение может быть адаптировано более легко. Я все еще думаю, что деревья сегментов являются жизнеспособной опцией для решения «O (log N)», но я не вижу, как сделать операцию 1 до сих пор. Вы отметили это с помощью spoj, можете ли вы ссылаться на проблему spoj? – IVlad

@IVlad Я также понял, что для ** умножить на v ** это может быть сделано деревом сегментов или двоичным индексированным деревом. Это не специфическая проблема spoj, но знание трюка поможет мне в решении нескольких проблем из spoj. –

Попытка работать с этим; Я также убежден, что сублинейный возможен. Я еще не полностью решил проблемы, но я готов поспорить, что это будет связано с тем, что (целые числа от '0' до' M-1', добавление по модулю 'M', умножение по модулю' M') образует поле. –

Так это выглядит, как у вас есть доступ ко всем элементам в пределах [i, j], сложность зависит от линейного размера этого диапазона,

источник

2013-08-21 14:29:11

Ну, первая операция может быть выполнена при сложении log (K) с использованием некоторых структур данных, где K - линейный размер этого диапазона. Возможно, второе может быть выполнено с той же сложностью, используя методы структуры данных. –

Затем найдите способ сделать это, не имея доступа ко всем элементам. : P –

@ DennisMeng - пока я обязательно попытаюсь это сделать, я не могу этого сделать, не докажу, что это невозможно. – IVlad

Вполне возможно, что дзи порядка N, и вы чтобы изменить каждый из них. Это делает любой алгоритм быстрее, чем O (N) невозможным, как сказал Павел. K не является параметром проблемы, это просто переменная, поэтому log (K) в ответе Bidhan не имеет смысла.

Теперь, если вопрос будет касаться не временной сложности, а о высоте дерева массивных параллельных операций (например, у вас есть на CUDA, например), то при заданном потоке один будет тривиально выполнять операцию 1 в O (1) из-за независимости всех операций и операции 2 в O (log (N)) путем умножения пар M mod смежных элементов (требуется 100000/2 потоков), затем пары смежных результатов и т. Д., Пока ответ получен.

Это был, однако, не вопрос. Запрет массового параллельного вычисления сложностью каждой операции - O (N), независимо от того, как вы это выполняете.

источник

2013-08-21 15:05:59 Michael

«вы должны изменить каждый из них» не следует. Даже если бы быстрее, чем «O (N)» было невозможно (что я очень сомневаюсь), это не доказательство. Вам не обязательно менять каждый из них, может быть достаточно сохранить определенную информацию о том, что они были изменены и все еще могут отвечать на запросы Operation 2. – IVlad

Да, как ** IVIad ** сказал, вам не нужно получать доступ к каждому элементу, чтобы рассчитать ответ. И, журнал (K) имеет прекрасный смысл для кого-то с некоторым знанием дерева сегментов. –

Множественность целых чисел в диапазоне

ответ

Смежные вопросы