前缀和
一维前缀和
for (int i = 1; i <= n; ++i)
{
pre[i] = pre[i - 1] + a[i];
}
二维前缀和
for (int i=1;i<=n;++i)
{
for (int j=1;j<=m;++j)
{
pre[i][j] = g[i][j]+pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1];
}
}
sum = pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1];
差分
一维差分
for (int i=1;i<=n;++i)
{
d[i] = a[i]-a[i-1]; //一维差分数组
}
二维差分
int a[n+1][m+1];
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]; //二维差分数组
} //减去左边、上边，加上左上角
}
//区间值的变化
d[x1][y1] += x;
d[x1][y2 + 1] -= x;
d[x2 + 1][y1] -= x;
d[x2 + 1][y2 + 1] += x;
for (int i=1;i<=n;++i)
{
for (int j=1;j<=m;++j)
{
d[i][j] = d[i][j]+d[i][j-1]+d[i-1][j]-d[i-1][j-1]; //二维前缀和还原成原数组
}
}
位运算
1.取第K位，x&(1<<(k-1))
2.~x\(\Leftrightarrow\)x!=-1
首先负数的二进制在计算机中以补码的形式存在，那么一个负数是怎么转变为补码的呢？
负数二进制的衍变过程： 原码-->反码-->补码
以-1为例
什么叫做原码？原码就是使最高位变为1，最高位也叫做符号位
0000 0001 --> 1000 0001
什么叫做反码？就是除了符号位之外，其余位全部取反
1000 0001 --> 1111 1110
什么叫做补码？就是在反码的基础上+1
1111 1110 --> 1111 1111
所以-1的补码就是255
那么~x，如果x==-1，则 ~x返回0；如果x!=-1，则 ~x返回1，所用 ~x 等价于 x !=-1
3.取一个整数最低位的1所代表的数，\(lowbit(x) = x与(-x);\)
引申：利用\(lowbit\)运算统计一个整数二进制形式下1的个数，同时也是树状数组的实现原理
原理：我们利用lowbit运算出最低位1代表的数，然后用原数减去这个数，往复循环，直到原数变为0
int cnt = 0;
while (x)
{
x -= x&(-x);
cnt++;
}
倍增
RMQ问题
ST表
ST表用来实现可重复贡献问题的数据结构，什么叫做可重复贡献问题？比如\(max(x,x)=x,gcd(x,x)=x\),所以RMQ问题和区间GCD就是一个可重复贡献问题，但是像区间和就不是了，因为会有重叠部分加到结果中，这部分结果是我们不愿意看到的，当然操作\(opt\)必须具有结合律，或者说自反性
ST 表模板题
题目大意：给定n个数，有q个询问，对于每个询问，你需要回答区间\([l,r]\)中的最大值。
考虑暴力做法。每次都对区间扫描一遍，求出最大值。
显然，这个算法会超时。
ST表基于倍增思想，预处理\(O (nlogn)\),询问\(O(1)\),但是不支持修改
我们令\(st[i][j]\)代表区间\([i,i+2^j-1]\)中的最大值
显然\(st[i][0]=a[i]\)
根据定义式，一步可以跳\(2^j-1\)步，我们可以知道一个区间$[i,i+2^j-1] $
可以二分为两个区间\([i,i+2^{j-1}-1]\)和\([i+2^{j-1},i+2^{j}-1]\)
所以一个状态可以有前一个状态推出，我们直接列出状态转移方程
\[st[i][j]=max(st[i][j-1],st[i+2^{j-1}][j-1]) \]以上就是预处理部分，复杂度\(O (nlogn)\)
假设 n=1e6
int st[n][22];
for (int j=1;j<=22;++j)
{
for (int i=1; i+(1<<(j-1))-1<=n ;++i)
{
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
对于询问：
回答区间\([l,r]\)中的最大值，因为是可重复贡献问题，所以我们只要用两个区间覆盖需要查询的区间即可，假设区间长度\(len=log_2(r-l+1)\)即把区间\([l,r]\)分为\([l,l+2^{len}-1]\)和\([r-2^{len}+1,r]\)
这两个区间一定能把\([l,r]\)覆盖，保证答案的正确性，我们直接列出回答
\[ans = max(st[l][len],st[r-(1<<len)+1][len]) \]题目背景
ST 表经典题——静态区间最大值
请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 \(O(1)\)。若使用更高时间复杂度算法不保证能通过。
快速读入作用仅为加快读入，并非强制使用。
题目描述
给定一个长度为 \(N\) 的数列，和 $ M $ 次询问，求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数 \(N,M\)，分别表示数列的长度和询问的个数。
第二行包含 \(N\) 个整数（记为 \(a_i\)），依次表示数列的第 \(i\) 项。
接下来 \(M\) 行，每行包含两个整数 \(l_i,r_i\)，表示查询的区间为 \([l_i,r_i]\)。
输出格式
输出包含 \(M\) 行，每行一个整数，依次表示每一次询问的结果。
样例 #1
样例输入 #1
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
样例输出 #1
9
9
7
7
9
8
7
9
提示
对于 \(30\%\) 的数据，满足 \(1\le N,M\le 10\)。
对于 \(70\%\) 的数据，满足 \(1\le N,M\le {10}^5\)。
对于 \(100\%\) 的数据，满足 \(1\le N\le {10}^5\)，\(1\le M\le 2\times{10}^6\)，\(a_i\in[0,{10}^9]\)，\(1\le l_i\le r_i\le N\)。
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e5 + 10;
int st[N][22];
int main(void)
{
Zeoy;
int t = 1;
// cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> st[i][0];
for (int j = 1; j <= 22; ++j)
{
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
{
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
while (m--)
{
int l, r;
cin >> l >> r;
int len = floor(log(r - l + 1) / log(2));
cout << max(st[l][len], st[r - (1 << len) + 1][len]) << endl;
}
}
return 0;
}