如何进一步优化支持永久更新的 prefix sum 队列问题？
结论
这个问题可以化简为动态维护数组的最小前缀和。使用线段树时，初始化复杂度为 (O(N))，每次永久更新的复杂度为 (O(\log N))，总复杂度为：
[ O(N+Q\log N) ]
这样无需在每次更新后重新计算完整的 prefix sum 和 suffix sum。
费用公式
假设等待前 (i) 个人离开，并贿赂其余的人，其中 (0\le i\le N)，费用为：
[ C_i=\sum_{j=1}^{i}A_j+\sum_{j=i+1}^{N}B_j ]
边界情况如下：
- (i=0)：贿赂所有人。
- (i=N)：不贿赂任何人，等待所有人离开。
令：
[ S_B=\sum_{j=1}^{N}B_j ]
可以得到：
[ \begin{aligned} C_i &=\sum_{j=1}^{i}A_j+S_B-\sum_{j=1}^{i}B_j\ &=S_B+\sum_{j=1}^{i}(A_j-B_j) \end{aligned} ]
再定义：
[ D_j=A_j-B_j ]
答案便可以写成：
[ \text{answer}=S_B+\min_{0\le i\le N}\left(\sum_{j=1}^{i}D_j\right) ]
当 (i=0) 时取空前缀，其前缀和为 0。
接下来只需维护所有 (B_j) 的总和 (S_B)，以及数组 (D) 的最小前缀和。
如何处理永久更新
每次更新的形式为：
A[k] = newA
B[k] = newB
这次操作只会改变：
[ D_k=A_k-B_k ]
同时需要更新：
[ S_B\mathrel{+}=newB-oldB ]
因此可以把它作为一次单点修改处理。线段树的每个节点保存两个值：
sum：该区间内所有 (D_j) 的和。minPrefix：该区间的最小前缀和，其中包含值为 0 的空前缀。
设当前节点由左区间 L 和右区间 R 合并，则：
sum = L.sum + R.sum
minPrefix = min(L.minPrefix, L.sum + R.minPrefix)
一个区间的前缀要么完全位于左区间，要么包含整个左区间和右区间的某个前缀。因此，根节点的 minPrefix 就是整个 (D) 数组的最小前缀和。
C++ 实现
以下代码按照题目和示例中的输入格式读取数据：先读 N，再读两个数组，最后读 Q。
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct Node {
int64 sum = 0;
int64 minPrefix = 0;
};
class SegmentTree {
private:
int n;
vector<Node> tree;
static Node mergeNode(const Node& left, const Node& right) {
Node result;
result.sum = left.sum + right.sum;
result.minPrefix = min(
left.minPrefix,
left.sum + right.minPrefix
);
return result;
}
void build(int node, int left, int right, const vector<int64>& d) {
if (left == right) {
tree[node].sum = d[left];
tree[node].minPrefix = min<int64>(0, d[left]);
return;
}
int mid = left + (right - left) / 2;
build(node * 2, left, mid, d);
build(node * 2 + 1, mid + 1, right, d);
tree[node] = mergeNode(tree[node * 2], tree[node * 2 + 1]);
}
void update(int node, int left, int right, int index, int64 value) {
if (left == right) {
tree[node].sum = value;
tree[node].minPrefix = min<int64>(0, value);
return;
}
int mid = left + (right - left) / 2;
if (index <= mid) {
update(node * 2, left, mid, index, value);
} else {
update(node * 2 + 1, mid + 1, right, index, value);
}
tree[node] = mergeNode(tree[node * 2], tree[node * 2 + 1]);
}
public:
explicit SegmentTree(const vector<int64>& d) {
n = static_cast<int>(d.size()) - 1;
tree.resize(4 * n + 4);
build(1, 1, n, d);
}
void update(int index, int64 value) {
update(1, 1, n, index, value);
}
int64 minimumPrefix() const {
return tree[1].minPrefix;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int64> a(n + 1);
vector<int64> b(n + 1);
vector<int64> d(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int64 sumB = 0;
for (int i = 1; i <= n; ++i) {
cin >> b[i];
sumB += b[i];
}
for (int i = 1; i <= n; ++i) {
d[i] = a[i] - b[i];
}
SegmentTree segmentTree(d);
auto answer = [&]() -> int64 {
return sumB + segmentTree.minimumPrefix();
};
int q;
cin >> q;
cout << answer();
while (q--) {
int index;
int64 newA, newB;
cin >> index >> newA >> newB;
sumB += newB - b[index];
a[index] = newA;
b[index] = newB;
d[index] = a[index] - b[index];
segmentTree.update(index, d[index]);
cout << ' ' << answer();
}
cout << '\n';
return 0;
}示例验证
初始状态为：
A = 2 7 3 5 1
B = 3 4 5 1 1
对应的 (D) 数组为：
D = A - B = -1 3 -2 4 0
算上空前缀，各个前缀和为：
0 -1 2 0 4 4
最小前缀和是 -1，同时：
sum(B) = 14
所以答案为：
14 + (-1) = 13
第一次更新后的答案是 8，第二次更新后的答案是 7。最终输出为：
13 8 7
注意事项
- 费用总和可能超过
int的范围，应使用long long。 - 计算时必须包含空前缀，所以叶节点的
minPrefix应设为min(0LL, value)。 - 普通 Fenwick Tree 能维护动态前缀和，却无法直接维护所有前缀和的最小值，不能单独用于解决这个问题。
- 题目描述和示例先读取
N，最后读取Q，而原代码使用cin >> TPeople >> TUpdates同时读取两者。如果实际评测也采用示例中的格式，需要像上面的代码一样分开读取。
备注：内容仅供参考。