能否用n阶差分维护区间加多项式?
  • 板块学术版
  • 楼主AffineRing
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/1/9 09:57
  • 上次更新2023/11/5 05:01:07
查看原帖
能否用n阶差分维护区间加多项式?
399250
AffineRing楼主2021/1/9 09:57

给原序列增加一个整式(ffk=0nakxk\sum_{k=0}^n a_kx^k 的点值时候,它的差分数组是不是发相当于增加了 ff'左右的整式?

所以是不是在原系列上每一个区间增加任何一个多项式都珂以用差分做?

  1. 例如原序列加 1 4 9 16...1\ 4\ 9\ 16 ...
  2. 那么差分后加 1 3 7 9...1\ 3\ 7\ 9 ...
  3. 再差分序列加 1 2 2 2...1\ 2\ 2\ 2 ...

然后是否就可以二阶差分了?

我的问题是:在原序列的一个区间上,每个数加上一个 nn 多项式在该位置的取值。这能否通过 nn 阶差分解决?

我目前只能想到如何修改,珂能只需要 O(1)O(1),如果不差分到底的话线段树或树状数组 log\log 级也能解决了。

但主要是单次查询的时候,似乎要达到 O(nm)O(nm)mm 是序列长度),因为我不知道怎么从差分数组在低于 O(1)O(1) 的时间里转化成原数组(除了 P1438\text P1438 那点我会做)。

或者说有哪些关于这方面的题目也可以推荐一下,谢谢各位!

2021/1/9 09:57
加载中...