DS
树状数组
原始问题
- \(a_x \overset+\gets y\)
- \(\sum\limits_{i=1}^{r} a_i\)
解决方法：
定义 \({\rm lb}(i) = i-i \wedge (i-1)\)
定义 \(f(i) = i \wedge (i-1)\)，\(f(0)=0\)。
可以发现 \(f^{\left\lfloor(\log_2 n+1)\right\rfloor}(n)=0\)。
另外地，\(\log_2 {\rm lb}(x)\) 正好是 \(x\) 的二进制表示 \(\sum\limits^{\infty}_{i=0}k_i2^i\) 的从右往左的第一个零的位置（最低位是 \(0\) 位），或者说 \({\rm lb}(x) = 2^{\min\{i \in \mathbf N \mid k_i=1\}}\)。
因此 \({\rm lb}(2^\lambda) = 2^\lambda(\lambda \in \mathbf N)\)。
考虑利用 \({\rm lb}\) 和 \(f\) 函数进行操作，将 \(1 \sim r\) 划分为 \(\le \log_2 n+1\) 的区间。
考虑化为 \((f(n),n]\)，可以通过一个数组 \(b\) 解决。
令 \(q\) 为前缀和数组，显然有 \(q_n = q_{f(n)} + b_n\)。
我们考虑修改操作，相当于解一个方程组 \(f(x) \le n\)，因为 \(f(x) = x - {\rm lb}(x)\)，所以 \(x - {\rm lb}(x) \le n \Longrightarrow {\rm lb}(x) \ge x-n\)，考虑枚举 \({\rm lb}(x) = r\)，可以发现满足条件的 \(x\) 最多只有一个：\(x = \left\lceil \dfrac n r\right\rceil r\)，但是有时求解出的 \({\rm lb}(x) \ne r\)，这时候说明 \({\rm lb}(n) > r\)，此时没有满足条件的解。
由于 \(f^{\left\lfloor(\log_2 n+1)\right\rfloor}(n)=0\)，所以统计一次前缀和的复杂度为 \(O(\log L)\)（L 为数组长度，下同），又因为对于每个 \({\rm lb}(x)\) 最多只有一个 \(x\)，而且 \({\rm lb}(x) = 2^\lambda(\lambda \in \mathbf N)\)，所以最多只有 \(\left\lfloor\log_2 L+1\right\rfloor\) 个解，所以单点修改的复杂度为 \(O(\log n)\)，完毕。
给出伪代码：
Variables:
T: Array[Int] // 树状数组变量
L: Int // 大小
Functions:
f(x: Int) -> Int = x & (x-1)
lb(x: Int) -> Int = x - f(x)
Query(ind: Int) -> Int = ans: // 查询前缀和
ans = 0
while ind != 0
ans = ans + T[ind]
ind = f(ind)
Modify(ind: Int, val: Int) -> Null:
t: Int = 1
while t <= L
x: Int = ceil(ind/t)*t
if lb(x) == t
T[x] = T[x] + val
t = 2t
树状数组的 modify 有一种等价写法：
Modify(ind: Int, val: Int) -> Null:
while ind <= L
T[ind] = T[ind] + val
ind = ind + lb(ind)
这个方法我暂时没有找到严格的数学证明，这里给一张图。
(贺的)
前缀修改，单点查询
- \(\forall i \in [1, R],a_i \overset+\gets y\)
- \(a_x\)
通过差分，可以轻松解决。
multiset 个数查询
- 删除一个 \([1, R]\)
- 加入一个 \([1, R]\)
- 求 \(x\) 在集合中出现了多少次
建立一个桶数组，删除就是 \(\forall i \in [1, R],a_i \overset-\gets 1\)，加入就是 \(\forall i \in [1, R],a_i \overset+\gets 1\)，于是转化为前缀修改，单点查询。有时需要离散化。这种方法叫做 权值树状数组。
动态 multiset 第 \(K\) 小
- 加入一个 \(x\)
- 删除一个 \(x\)
- 求集合第 \(K\) 小
考虑权值树状数组，12 操作显然，3 操作可以直接二分，查询从 \(0 \sim x\) 的个数，转化为单点修改，前缀查询，注意，\(3\) 操作的时间复杂度为 \(O(\log^2 L)\)
二维偏序
考虑逆序对问题：建立权值树状数组，每次先插入 \(a_i\)，然后查询 \((a_i,\max a]\) 的个数（因为此时进这个集合的一定下标 \(\le i\)，而且 \(a_i \not> a_i\)，所以是 \(i<j \wedge a_i>a_j\) 的个数），通过建立第一维的顺序可以求二维偏序。
前缀修改，前缀查询
- \(\forall i \in [1, R],a_i \overset+\gets y\)
- \(\sum\limits_{i=1}^{r} a_i\)
考虑差分。题目变为
- \(a_i \overset+\gets y\)
- \(\sum\limits^{R}_{i=1}\sum\limits^{i}_{j=1} a_j=\sum\limits^{R}_{i=1} (R-i+1)a_i=\sum\limits^{R}_{i=1} Ra_i-ia_i+a_i=(R+1)\sum\limits^{R}_{i=1}a_i-\sum\limits^{R}_{i=1}ia_i\)
考虑维护两个树状数组，分别维护 \(a_i\) 和 \(ia_i\)，即可解决。
PM+PPQ
- \(\forall i \in [1, R],a_i \overset+\gets y\)
- \(\sum\limits_{i=1}^{r} \sum\limits_{j=1}^{i} a_j\)
考虑差分。题目变为
- \(a_i \overset+\gets y\)
- \(\sum\limits^{R}_{i=1}\sum\limits^{i}_{j=1}\sum\limits^{j}_{k=1} a_k=\sum\limits^{R}_{i=1}(i\sum\limits^{i}_{j=1}a_j)+\sum\limits^{R}_{i=1}(\sum\limits^{i}_{j=1}a_j)-\sum\limits^{R}_{i=1}\sum\limits^{i}_{j=1}ja_j-\text{Lazy,懒得退了，反正里面是一个多项式}\)
最新文章
- selenium webdriver 右键另存为下载文件（结合robot and autoIt）
- TFS API：一、TFS 体系结构和概念
- 客户端用javascript获取文件大小
- Transaction Save Point (SET XACT_ABORT { ON | OFF })
- ACM: The Suspects-并查集-解题报告
- Jquery设置select控件指定text的值为选中项
- Target Operator ID has No Access to Upgrade
- jQuery 、js 设置 显示隐藏
- HDU-1527 取石子游戏
- FATE（完全背包）
- Fedora 启动 SSH服务
- Linux--线程安全与可重入函数的异同
- JavaScript中的面向对象程序设计
- oracle自动备份_expdp_Linux
- Latex常用软件
- 网络运维必回的模拟器-GNS软件下载和安装
- Windows PowerShell 入門（2）－基本操作編 2
- linux 查找并kill进程
- 20155208徐子涵 2016-2017-2 《Java程序设计》第5周学习总结
- Android JNI的使用方法