求和、差分、哈希 | EVA'S WONDERLAND

Colin 课堂开课啦 ~ ~ 孩子代码总不会，多半是学不会啦！（不是

复杂度

先来说说关于复杂度的事情，为什么要关注一个算法的复杂度嘞？（因为不关注会 TLE

首先，常见的计算机运算能力大概是 3e7 ，这是常识（不是

根据上面的常识，我们来列列如下的表格：

再比如，如果一个题，它的数据范围大概是5000，那么我们要选的算法的复杂度可能是或等

（学了复杂度，大概就能知道，我写的代码大部分都会 TLE）

离散的积分和微分

离散的积分，其本质为求和；离散的微分，其本质为差分。

给定一组数列，我们可以分别用积分和微分的想法求

$a_k = \sum_{i = 1}^k (a_i - a_{i - 1}) = \sum_{i = 1}^k a_i - \sum_{i = 1}^{k - 1} a_i$

例1（求和）

给定一组数列，共有次询问，每次询问给出一组和，问到的和。

解1

如果暴力直接做，复杂度是大概是级别的，而的范围为，所以不能暴力做。

我们可以发现，要求到的和，可用如下公式

$\sum_{i = l}^r a_i = \sum_{i = 1}^r a_i - \sum_{i = 1}^{l - 1} a_i$

我们记，则上面的公式可表示为。

那么，问题就转换为，对于每个位置，求出从到的和。

如果暴力对每个位置求从到的和，复杂度还是。观察可发现有如下式子成立，用此方法求前缀和。

综上，该算法的复杂度为

例2（差分）

给定一组数列，共有次询问，每次询问给出一组，对从到范围里的数，次问询后，输出数列的每一项。

解2

如果暴力直接做，复杂度是大概是级别的，而的范围为，所以不能暴力做。

利用积分微分思想求，我们利用等式的前半部分即，若令

注：且

那么每一次操作就相当于，

综上，该算法的复杂度为

练1

给定一组数列，共有次询问，每次询问给出一组，对从到范围里的数。次问询后，输出数列的每一项。

#include <bits/stdc++.h>
#define N 1000007
using namespace std;

int a[N], b[N], c[N];

int main(){
	int n, q, l, r;
	cin >> n >> q;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		b[i] = a[i] - a[i - 1];
		c[i] = b[i] - b[i - 1];
	}
	
	while(q--){ //l & r 从1开始数 
		cin >> l >> r;
		c[l] += 1;
		c[r + 1] -= r - l + 2;
		c[r + 2] += r - l + 1;
	}
	for(int i = 1; i <= n; ++i){
		b[i] = b[i - 1] + c[i];
		a[i] = a[i - 1] + b[i];
		cout << a[i] << ' ';
	}
	return 0;
}

两次差分，最后两次求和。

练二

https://codeforces.com/gym/102770/problem/A

串（哈希篇）

哈希是用来干啥的呢？？我们想用哈希来干啥呢？？？

字符串一般比较长，且比较难处理，但一般来说，数字是比较好处理的。所以我们想构造一个，字符串和数字之间的一种双射关系。受各种进制相互转换的感发，我们尝试把字符串看作一种进制，并让该字符串与转换为十进制的数字相对应。举个例子，假设我们有个字符串 abdc 因为这个串中只有4个不同的字符，我们可以选定 （>4即可），并按字母的顺序，视，则该字符串对应的数字为。在计算的同时，我们能发现一个问题，就是这个数字可能会很大，甚至超出 int 所能存储的范围。为了解决这个问题我们选择取模的方式，将数字控制在一定的范围之内。

为了减少 哈希冲突 （取模后两个不同字符串对应数字相同），我们需要选一个大质数作为模数，通常会选用或。若想更近一步减少哈希冲突，我们可以选择“哈哈”（双哈），即让一个字符串对应的数字分别对两个不同的大质数取模。对于两个字符串，只有当两个取模后的数都相同时，我们才认为这两个字符串相等。“哈哈”能十分有效避免哈希冲突。

秦九昭

如果字符串很长，那我们就需要 base 的高次运算。就算使用快速幂，这个过程也会十分麻烦。故我们采用下面的计算方式，还引用上面的例子，对应数字将如下计算。

这个式子有什么好处呢？

计算方便
我们观察能发现，这个式子括号里面的值，就是该字符串从开头到当前字符的哈希值。什么意思呢？还引用上面的例子。是对应的值，而是对应的值，以此类推。故这个式子，可以利用前一项已知串的哈希值计算出后一项的哈希值。

例1

https://loj.ac/p/103

解1

根据 秦九昭 我们可以很方便的计算出，即从第个字符到第个字符这个字符串对应的哈希值。那么我们要怎么得到字符串里每一个长度为子串的哈希值呢？经过思考不难得出如下式子：。故要判断串在串中出现的次数，只需要依次比较中长度为的字串的哈希值是否与串的哈希值相同即可。

不要忘记取模，在任何可能出现过大数字的地方都要及时取模。
取模前若有可能出现负数，则应该先，再。

#include <bits/stdc++.h>
#define N 1000007
#define base 53
#define mod 1000000007
using namespace std;

char a[N], b[N];
int h[N], B[N];

int get(char c) {
    if (c <= 'Z' && c >= 'A')
        return c - 'A';
    else
        return c - 'a' + 32;
}

int hh(int l, int r) {
    return (h[r] - 1ll * h[l - 1] * B[r - l + 1] % mod + mod) % mod;
}

int main() {
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    int n = strlen(a + 1);
    int m = strlen(b + 1);
    int cnt = 0, hash = 0;

    for (int i = 1; i <= m; ++i)
        hash = (1ll * hash * base + get(b[i])) % mod;

    B[0] = 1;

    for (int i = 1; i <= n; ++i) {
        B[i] = 1ll * B[i - 1] * base % mod;
        h[i] = (1ll * h[i - 1] * base + get(a[i])) % mod;
    }

    for (int i = m; i <= n; ++i)
        if (hh(i - m + 1, i) == hash)
            cnt++;

    cout << cnt << endl;
    return 0;
}

常用 base: 31 53 mod: 1e9+7 (双哈 mod2 = 1e9+9)

跟Co老师学习好累……