Поддержание значения многочлена над динамически обновляемым вводом

Пусть - многочлен над фиксированным конечным полем. Предположим, что нам задано значение P для некоторого вектора y ∈ { 0 , 1 } n и вектора y .$P(x_1, x_2, \ldots, x_n)$$P$$y \in \{0,1\}^n$$y$

Теперь мы хотим вычислить значение на вектор у ' ∈ { 0 , 1 } п такая , что у и у ' отличаются по точности одной позиции (другими словами, мы переворачивать ровно один бит в у ). Каковы пространство и время компромиссов для этой проблемы?$P$$y' \in \{0,1\}^n$$y$$y'$$y$

Например, если это число одночленов в P , мы можем хранить коэффициенты и значения всех мономов P . Если y i перевернуто, мы фиксируем значение каждого монома, содержащего y i, а затем значение P ( y ), используя сохраненную информацию. В общем, нам нужно O ( r ) время и пространство.$r$$P$$P$$y_i$$y_i$$P(y)$$O(r)$

(Я ничего не говорю о том, как мы идентифицируем мономы, содержащие для цели. Вы можете выбрать любое разумное представление P , в примере, который я предполагаю, что мы храним список мономов, содержащих y i, для каждого i .)$y_i$$P$$y_i$$i$

есть что-нибудь получше?

Ваша идея обобщается следующим образом: с учетом алгебраической схемы (над конечным полем) или логической схемы (вычисление побитового представления ваших элементов конечного поля) вычисляя , затем сохраняйте значение в каждом элементе схемы. Когда вы меняете i-й бит y , просто распространяйте это изменение по DAG схемы, начиная со входа y i . Если схема имеет размер s , это занимает O ( s ) время и пространство. Это может быть намного меньше, чем количество мономов (что соответствует размеру алгебраических схем глубиной только 2).$P$$i$$y$$y_i$$s$$O(s)$

Легко изменить подход хранения мономов, чтобы каждое обновление занимало время, пропорциональное количеству измененных мономов: просто обновите общее значение полинома, добавив новое значение и вычтя старое значение для каждого измененного монома.

$P$$P$$k$$O(k\log N)$$N$