爵士OIer查看:26 回复:45 评论:26 创建时间:2021-01-26T18:52:12用户:爵士OIer查看:26 回复:45 评论:26 创建时间:2021-01-26T18:52:12
大家好！这里是Kitten进阶教程与实战的第一期。相信跟着爵士来，大家的Kitten创作水平会大大提高。
我们将在这些教程里学习一些适合进阶深造的算法和技巧。
其实之前是发过的，当时因为太晚所以弄得很乱，而且还很多细节都没讲。
现在这篇帖子在原来的帖子基础上广为补充、发展，由一堆乱七八糟的字变成了一篇完美的教程。
目录：
什么是列表，基本用途
列表的插入
用列表实现数据处理
进阶算法和数据结构
前缀和算法
分块算法
什么是列表，基本用途
我们的Kitten上的列表，就我看来是一类线性数据，最有可能是数组。
列表内存储了一系列变量，这些变量的排列方式为线性排列。
举个最简单的例子，你将一堆苹果排成一列。把变量理解为苹果，当你要对苹果进行操作的时候，你必须在这一列中操作。
你能支持的基本操作有：任意获知一个苹果是什么样的；交换两个苹果；将一个苹果替换为一个新的苹果。
我们就要用这些基本操作来处理变量。别看这些操作非常简单，却是Kitten和语言编程中实现程序的最基本的操作和方式。
列表的插入
当我们需要执行一些稍复杂的运作的时候，我们只需将其组合。
这里讲解了如何插入元素。
插入元素100到第100项的积木如下：
并不难理解，大家自己画一下图就行了。
思路是把从100项开始的每一个元素都向后移一位，然后再把第100项替换为100。
下面是过程解释：
如果你希望更加生动的解释，看这张图
用列表实现数据处理
其实我们发现在Kitten中，列表的很多内容都已经给你封装好了。
这个时候我们拖动若干积木，就能够实现一些数据处理。
列表有以下基本操作：
还可以做到获取元素
判断长度
我们来一个实例吧。
我们想要寻找一个列表中的最大值，怎么办？
我想很多人看到这里就已经有答案了：我们将列表中一个一个的比对过去，用一个值Max记录列表最大值。
大家看看积木怎么拼吧：
在这里，我们使用 i 遍历了整个列表，用Max记录最大值。
进阶算法和数据结构
这是本期教程的重点和难点。
问题引入
如何给列表的一部分 [left, right] 求和？
大家经过上面的学习，应该完成这个任务。这可能要花一点时间来思考。
我们还是用上面的遍历方法，但是这次是从 left 到 right 了。
前缀和算法
如果现在我要在短时间内多次求出某些区间的和，我该怎么办？
众所周知，Kitten的重复执行是由等待时间的。因此如果序列长度稍长、询问次数稍多，那么程序就要花费很长时间。
请大家思考，除了每次都向上面那样求一遍，我们还有什么方法？
不知道你们有没有这么想过：我用另一个列表 S，第 i 个位置存储从第1项到第 i 项的和。
这样做有什么好处？这是值得思考的。我想大家画画图就非常清楚了。
珂能图有点鬼，但是翻译一下就是
原序列：a1,a2,a3,a4,a5,a6,a7
我要算出：a3+a4+a5
这个就等于：a1+...+a5-(a1+a2)
同样如果我要求a4+a6，则可以转化为 a1+...+a6-(a1+...+a3)
我们看下面这张图，加深理解：
看到没有，原序列为红色线段，我要求蓝色的一段，它就等于绿色一段减去棕色一段！
上面的 S 数组就是对原数列 a 的求和。我们每次询问 Sum(left,right) 的时候，只需用S的第right项减喵的第left-1项即可！
这便是我们的前缀和算法。
我们用Kitten实现就很简单啦，下面是建立列表 S 的过程：
那么我们处理询问的时候，按照上述即可。
分块算法
但是假如我们需要对序列进行修改呢？
这个时候前缀和也不管用啦，因为修改之后前缀和数组 S 也要跟着发生一连串的变化了。
怎么办？
以一个简单的例子为例。我们需要支持在线修改，每次给某一个数增加一个值 delta。
不知道你们有没有想到：将一系列的数捆绑在一起，算出他们的和。需要询问的时候，如果包含这些数，我们直接给出一个总和，就不需要一个个去算了。
看上面这张图。我们将数两个两个的捆绑在一起。当询问从第一个到第四个的和的时候，因为我们之前已经知道了每两个数的和，因此算的时候直接拿3+9就行了。
如何处理给某一个数增加 delta？
我们只需要进行两步：第一步，给这个数增加delta；第二步，给这个数所属的那一捆的总和增加 delta 即可。
但是有一个问题，如果要计算的不是完整的一部分怎么办？
不用动太多脑筋啦，直接一个一个累计就行了。
因此我们也要合理分配捆绑的方式。我们不能绑的个数太多，也不能一捆里面装太多的数。如果捆绑的个数多到和原序列的项数一样多，或者一捆大到包含了原来整个数列，这就相当于没有分块了。
话说回来，想到不能太多也不能太少，你想到了什么？
没错，开方！
因此我们将序列分为根号 n 块，要询问时整块直接累加；零碎的再单独累加。
这就是分块算法。我们容易发现具有大段维护，小段朴素的思想。
Code：
long long a[100010], sum[100010], add[100010];
int L[100010], R[100010]; // 每段左右端点
int pos[100010]; // 每个位置属于哪一段
int n, m, t;
void change(int x, long long d) {
int p = pos[x];
a[x] += d;
sum[p] += d;
}
long long ask(int l, int r) {
int p = pos[l], q = pos[r];
long long ans = 0;
if (p == q) {
for (int i = l; i <= r; i++) ans += a[i];
ans += add[p] * (r - l + 1);
}
else {
for (int i = p + 1; i <= q - 1; i++)
ans += sum[i] + add[i] * (R[i] - L[i] + 1);
for (int i = l; i <= R[p]; i++) ans += a[i];
ans += add[p] * (R[p] - l + 1);
for (int i = L[q]; i <= r; i++) ans += a[i];
ans += add[q] * (r - L[q] + 1);
}
return ans;
}
// 分块
t = sqrt(n*1.0);
for (int i = 1; i <= t; i++) {
L[i] = (i - 1)*sqrt(n*1.0) + 1;
R[i] = i*sqrt(n*1.0);
}
if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
// 预处理
for (int i = 1; i <= t; i++)
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
sum[i] += a[j];
}
我想 change 和 ask 大家自己都能够写出来，主要是把分块的那部分放一下。
结语
本期教程就到这里了。
我们学会了列表进阶操作、前缀和算法和分块算法。
接下来一期，我们将踏入函数，学习搜索算法。
