洛谷 P4868 分析（别看）

科技起源

2026-07-09 11:42:09

发布于：河北

4阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体值

1.2 题目背景、允许、禁止与限制

背景：

有一个由 $n$ 个数字组成的序列 $a$
定义数列前缀和为 $S_i=S_{i-1}+a_i$
定义数列前前缀和为 $SS_i=SS_{i-1}+S_i$

允许：有两种操作

一种是“修改”：在 $i$ 位置把 $a_i$ 改成 $x$ （同时 $S_i$ 和 $SS_i$ 也要同步修改）
一种是查询：查询 $i$ 位置上的 $SS_i$

禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n,m \le 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一个序列，定义了一个“前缀和”和“前前缀和”，有两种操作，对于每次查询输出具体结果

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 分情况考虑

2.4 数学

2.4.1普通前缀和：

原数组： $a_1=1,\ a_2=2,\ a_3=3,\ a_4=4,\ a_5=5$

$S_i$ 的意思：前 $i$ 个 $a$ 全部加起来

$S_1 = a_1 = 1$
$S_2 = a_1 + a_2 = 1 + 2 = 3$
$S_3 = a_1 + a_2 + a_3 = 1 + 2 + 3 = 6$
$S_4 = a_1 + a_2 + a_3 + a_4 = 1 + 2 + 3 + 4 = 10$
$S_5 = a_1 + a_2 + a_3 + a_4 + a_5 = 1 + 2 + 3 + 4 + 5 = 15$

2.4.2 前前缀和：

现在把上面算出来的 $S_1、S_2、S_3、S_4、S_5$ 当成新数组，再算一遍前缀和，结果就是 $SS_i$ 。

$SS_i = S_1 + S_2 + S_3 + \dots + S_i$

2.4.3 拆分 $SS$

我们把 $SS_5 = 1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5)$ 全部展开，去掉括号：

$\begin{aligned} SS_5 &= 1 \\ &+ 1 + 2 \\ &+ 1 + 2 + 3 \\ &+ 1 + 2 + 3 + 4 \\ &+ 1 + 2 + 3 + 4 + 5 \end{aligned}$

现在数每个数字出现几次：

数字 $1$ （ $a_1$ ）：一共出现 $5$ 次
数字 $2$ （ $a_2$ ）：一共出现 $4$ 次
数字 $3$ （ $a_3$ ）：一共出现 $3$ 次
数字 $4$ （ $a_4$ ）：一共出现 $2$ 次
数字 $5$ （ $a_5$ ）：一共出现 $1$ 次

规律：
求 $SS_i$ 的时候，第 $k$ 个数字 $a_k$ ，会出现 $(i - k + 1)$ 次。

2.4.4 整理公式

根据前面找到的规律，第 $k$ 个数字 $a_k$ 在 $SS_i$ 里要乘 $(i-k+1)$ ，所以整体式子是：

$\begin{aligned} SS_i &= a_1 \times (i - 1 + 1) + a_2 \times (i - 2 + 1) + \dots + a_i \times (i - i + 1) \\ &= a_1 \times i + a_2 \times (i - 1) + \dots + a_i \times 1 \end{aligned}$

第一步：单独拿出任意一项 $a_k \times (i-k+1)$ ，拆分括号

我们只看其中任意一个小项： $a_k \times (i - k + 1)$
先调整括号里数字的顺序，重新分组：

$i - k + 1 = (i + 1) - k$

把变形后的括号代回原式：

$a_k \times \big[(i+1) - k\big]$

用乘法分配律，把 $a_k$ 分别乘进括号里的两个数：

$a_k \times (i+1) - a_k \times k$

于是得到单项变形公式：

$a_k \times (i - k + 1) = a_k \times (i + 1) - a_k \times k$

第二步：把 $k=1$ 到 $k=i$ 的所有项全部代入求和

$SS_i$ 是 $k$ 从1加到 $i$ 的所有单项相加，写成求和符号：

$SS_i = \sum_{k=1}^i a_k \times (i - k + 1)$

把上面变形好的单项替换进去：

$SS_i = \sum_{k=1}^i \Big[ a_k \times (i+1) - a_k \times k \Big]$

求和可以拆开，变成两个求和式子相减：

$SS_i = \sum_{k=1}^i a_k \times (i+1) \quad-\quad \sum_{k=1}^i a_k \times k$

第三步：把常数 $(i+1)$ 提到求和符号外面

$(i+1)$ 只和查询的下标 $i$ 有关，和循环变量 $k$ 没有关系，每一项都有这个数，可以直接提取出来：

$\sum_{k=1}^i a_k \times (i+1) = (i+1) \times \sum_{k=1}^i a_k$

第四步：合并得到最终计算公式

把提取常数后的式子代回去：

$SS_i = (i + 1) \times \sum_{k=1}^i a_k \;-\; \sum_{k=1}^i \big(a_k \times k\big)$

去掉求和符号，写成直观展开形式：

$SS_i = (i + 1) \times \big(a_1 + a_2 + \dots + a_i\big) - \big(a_1 \times 1 + a_2 \times 2 + \dots + a_i \times i\big)$

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：单点修改，区间修改，单点查询 $\longrightarrow$ $\huge{树状数组}$

3.1 ※重点※

既然我们已经推出了：

$SS_i = (i + 1) \times \big(a_1 + a_2 + \dots + a_i\big) - \big(a_1 \times 1 + a_2 \times 2 + \dots + a_i \times i\big)$

我们就可以维护两个树状数组
一个负责求 $\big(a_1 + a_2 + \dots + a_i\big)$ ，一个负责求 $\big(a_1 \times 1 + a_2 \times 2 + \dots + a_i \times i\big)$
因为 $i+1$ 是固定的，加减乘除顺序也是固定的，因此这样没问题

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m;
const int N = 1e5 + 10;
int a[N];
int fir[N], sec[N];

int lowbit(int num){
	return num & (-num);
} 
void add1(int i, int num){
	int t = i;
	while(t <= n){
		fir[t] += num;
		t += lowbit(t); 
	}
	return ;
}
int getsum1(int t){
	if (t == 0){
		return 0;
	}
	return fir[t] + getsum1(t - lowbit(t));
}
void add2(int i, int num){
	int t = i;
	while(t <= n){
		sec[t] += num;
		t += lowbit(t); 
	}
	return ;
}
int getsum2(int t){
	if (t == 0){
		return 0;
	}
	return sec[t] + getsum2(t - lowbit(t));
}

signed main(){
	
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		add1(i, a[i]);
		add2(i, a[i] * i);
	}
	while(m--){
		string s;
		cin >> s;
		if (s == "Query"){
			int l;
			cin >> l;
			int gs1 = (l + 1) * getsum1(l);
			int gs2 = getsum2(l);
			cout << gs1 - gs2 << endl;
		} else {
			int l, x;
			cin >> l >> x;
			add1(l, (x - a[l]));
			add2(l, (x - a[l]) * l);
			a[l] = x;
		}
	}
	
	return 0;
}