【C++】数据结构|区间查询类问题模板
本文主要记录常见的区间查询问题算法及其相关问题的代码，方便博主自己快速查找。
为了方便区分什么时候选择哪个模板，这里附上一张选择图表。
假设序列长度为 N，操作次数为 M。
| 算法/数据结构 | 适用范围 (核心能力) | 建树/预处理 | 单点修改 | 区间修改 | 区间查询 | 代码量 | 常数 | 空间 |
| 前缀和/差分 | 静态查询 / 离线修改 | O(N) | O(N) | O(1)∗ | O(1) | 极小 | 极小 | O(N) |
| ST表 | 静态 RMQ (最值/GCD) | O(NlogN) | 不支持 | 不支持 | O(1) | 小 | 小 | O(NlogN) |
| 树状数组 (BIT) | 可加和信息 | O(N) | O(logN) | O(logN)† | O(logN) | 小 | 极小 | O(N) |
| 线段树 | 通用区间维护 (最值/和/复杂逻辑) | O(N) | O(logN) | O(logN) | O(logN) | 大 | 大 | O(4N) |
| 分块 | 根号平衡，无法快速合并的信息 | O(N) | O(1) | O(N) | O(N) | 中 | 小 | O(N) |
| 平衡树 | 动态 插入/删除/区间翻转 | O(NlogN) | O(logN) | O(logN) | O(logN) | 极大 | 极大 | O(N) |
| 带修莫队 | 离线、带单点修改的区间查询 | O(MlogM) | 支持 (视作时间维) | 不支持 | O(N5/3) | 中 | 小 | O(N+M) |
O(logN)†：树状数组通过维护两个数组可以支持区间修改区间查询，但局限性较大（通常仅限求和）。
前缀和/差分
最简单和最常用的算法之一，这里不再赘述。
(值得一提的是异或也可以维护“前缀异或”/”异或差分” 原因为异或和加减法运算性质相同，均可逆)
ST 表
ST 表（Sparse Table，稀疏表）通过倍增法预处理，利用可重复贡献的原理解决区间查询问题。（可重复贡献：例如求最值，不管重复覆盖与否，最大的就是最大的。与加法不同，如果重复了结果就不一样了）
ST 表不支持修改操作。
最值/按位与/按位或/gcd
题目：P3865 【模板】ST 表 & RMQ 问题（https://www.luogu.com.cn/problem/P3865）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m, x, y;
cin >> n >> m;
int lgn = log2(n);
vector<vector<int>> st(n + 1, vector<int>(lgn + 1));
for (int i = 1; i <= n; i++) cin >> st[i][0];
for (int j = 1; j <= lgn; 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]); // 预处理最大值
st[i][j] = st[i][j - 1] & st[i + (1 << (j - 1))][j - 1]; // 预处理按位与
st[i][j] = st[i][j - 1] | st[i + (1 << (j - 1))][j - 1]; // 预处理按位或
st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); // 预处理gcd
}
}
while (m--)
{
cin >> x >> y;
int len = log2(y - x + 1);
cout << max(st[x][len], st[y - (1 << len) + 1][len]) << "\n"; // 查询最大值
cout << (st[x][len] & st[y - (1 << len) + 1][len]) << "\n"; // 查询按位与
cout << (st[x][len] | st[y - (1 << len) + 1][len]) << "\n"; // 查询按位或
cout << gcd(st[x][len], st[y - (1 << len) + 1][len]) << "\n"; // 查询gcd
}
return 0;
}
树状数组(BIT)
利用树形结构和二进制的性质维护的一种很高效的数据结构。对于可以维护的问题往往优于线段树，也好写很多。
可以维护的数据与ST 表正好相反，数据必须是能“合二为一”（如加法、乘法）且运算可逆的。
单点修改/区间查询
题目：P3374 【模板】树状数组 1（https://www.luogu.com.cn/problem/P3374）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#define lowbit(x) (x & -x)
using namespace std;
using ll = long long;
vector<ll> arr, tree;
int n;
void add(int x, int k)
{
while (x <= n)
{
tree[x] += k; // 维护求和
tree[x] ^= k; // 维护异或
x += lowbit(x);
}
}
ll query(int x)
{
ll sum = 0;
while (x > 0)
{
sum += tree[x]; // 维护求和
sum ^= tree[x]; // 维护异或
x -= lowbit(x);
}
return sum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m, op, x, k;
cin >> n >> m;
arr.resize(n + 1);
tree.resize(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
add(i, arr[i]);
}
while (m--)
{
cin >> op;
if (op == 1)
{
cin >> x >> k;
add(x, k);
}
else
{
cin >> x >> k;
cout << (query(k) - query(x - 1)) << endl; // 查询求和
cout << (query(k) ^ query(x - 1)) << endl; // 查询异或
}
}
return 0;
}区间修改/单点查询
其实就是把上面的前缀和换成差分，最后还原即可。
题目：P3368 【模板】树状数组 2（https://www.luogu.com.cn/problem/P3368）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#define lowbit(x) (x & -x)
using namespace std;
using ll = long long;
vector<ll> arr, tree;
int n;
void add(int x, int k)
{
while (x <= n)
{
tree[x] += k; // 维护求和
tree[x] ^= k; // 维护异或
x += lowbit(x);
}
}
ll query(int x)
{
ll sum = 0;
while (x > 0)
{
sum += tree[x]; // 维护求和
sum ^= tree[x]; // 维护异或
x -= lowbit(x);
}
return sum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m, op, x, y, k;
cin >> n >> m;
arr.resize(n + 1);
tree.resize(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
add(i, arr[i] - arr[i - 1]); // 维护求和
add(i, arr[i] ^ arr[i - 1]); // 维护异或
}
while (m--)
{
cin >> op;
if (op == 1)
{
cin >> x >> y >> k;
// 维护求和
add(x, k);
add(y + 1, -k);
// 维护异或
add(x, k);
add(y + 1, k);
}
else
{
cin >> x;
cout << query(x) << endl;
}
}
return 0;
}区间修改/区间查询
参考上面俩代码，其实可以通过维护两棵树状数组解决。
对于异或则稍有不同：
题目：P3372 【模板】线段树 1（https://www.luogu.com.cn/problem/P3372）
C++
#include <iostream>
#include <algorithm>
#include <vector>
#define lowbit(x) (x & -x)
using namespace std;
using ll = long long;
vector<ll> arr, tr1, tr2;
int n;
void add(vector<ll>& tree, ll x, ll k)
{
while (x <= n)
{
tree[x] += k; // 维护求和
tree[x] ^= k; // 维护异或
x += lowbit(x);
}
}
ll query(vector<ll>& tree, ll x)
{
ll sum = 0;
while (x > 0)
{
sum += tree[x]; // 维护求和
sum ^= tree[x]; // 维护异或
x -= lowbit(x);
}
return sum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m, op;
ll x, y, k;
cin >> n >> m;
arr.resize(n + 1);
tr1.resize(n + 1);
tr2.resize(n + 1);
for (ll i = 1; i <= n; i++)
{
cin >> arr[i];
// 维护求和
add(tr1, i, arr[i] - arr[i - 1]);
add(tr2, i, (arr[i] - arr[i - 1]) * (i - 1));
// 维护异或
add(tr1, i, arr[i] ^ arr[i - 1]);
if (!(i & 1)) add(tr2, i, arr[i] ^ arr[i - 1]);
}
while (m--)
{
cin >> op;
if (op == 1)
{
cin >> x >> y >> k;
// 维护求和
add(tr1, x, k);
add(tr1, y + 1, -k);
add(tr2, x, k * (x - 1));
add(tr2, y + 1, -k * y);
// 维护异或
add(tr1, x, k);
add(tr1, y + 1, k);
if (!(x & 1)) add(tr2, x, k);
if (!((y + 1) & 1)) add(tr2, y + 1, k);
}
else
{
cin >> x >> y;
// 维护求和
cout << query(tr1, y) * y - query(tr2, y) - (query(tr1, x - 1) * (x - 1) - query(tr2, x - 1)) << endl;
// 维护异或
ll prey = query(tr2, y);
if (y & 1) prey ^= query(tr1, y);
ll prex = query(tr2, x - 1);
if ((x - 1) & 1) prex ^= query(tr1, x - 1);
cout << (prey ^ prex) << endl;
}
}
return 0;
}O(n) 建树
除了上面的利用add函数建树（时间复杂度O(n logn)），我们还可以直接利用树状数组的树结构在O(n)的时间复杂度完成建树。
C++
void init()
{
for (int i = 1; i <= n; i++)
{
tree[i] += arr[i];
int j = i + lowbit(i);
if (j <= n) tree[j] += tree[i];
}
}求逆序对
主要思想为：把树状数组的下标当成桶，统计各数字出现次数。每次加入一位数字，这样查询前缀和时得到的就是小于等于当前数字的数字个数（因为是按大小顺序加入的）。再用当前已加入树状数组的数字总量减去小于等于的个数，得到的便是这位数字前面大于他的数字数量。
题目：P1908 逆序对（https://www.luogu.com.cn/problem/P1908）
题目数字的范围可以达到1e9，直接建树显然MLE。这时候我们需要对数据进行离散化处理：即排序去重后生成一个一一对应的大小关系表。比如数据 [10, 99999, 20]，它们的大小关系等同于 [1, 3, 2]。
C++
#include <iostream>
#include <vector>
#include <algorithm>
#define lowbit(x) (x & -x)
using namespace std;
using ll = long long;
vector<ll> arr, tree, rk;
int n;
void add(int x, int k)
{
while (x <= n)
{
tree[x] += k;
x += lowbit(x);
}
}
ll query(int x)
{
ll sum = 0;
while (x > 0)
{
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
arr.resize(n);
for (auto& i : arr) cin >> i;
rk = arr;
sort(rk.begin(), rk.end());
rk.erase(unique(rk.begin(), rk.end()), rk.end());
tree.resize(rk.size() + 1);
ll res = 0;
for (int i = 0; i < n; i++)
{
ll id = lower_bound(rk.begin(), rk.end(), arr[i]) - rk.begin() + 1;
res += i - query(id);
add(id, 1);
}
cout << res << endl;
return 0;
}线段树
线段树是利用分治思想建立的维护区间信息的二叉树。
单点修改
题目：P3374 【模板】树状数组 1（https://www.luogu.com.cn/problem/P3374）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#define lc p<<1
#define rc p<<1|1
using namespace std;
using ll = long long;
struct SegTree
{
struct node
{
ll l, r, v;
};
vector<node> tree;
SegTree(vector<ll>& arr)
{
tree.resize(4 * arr.size());
build(arr, 1, 1, arr.size() - 1);
}
void pushup(ll p)
{
tree[p].v = tree[lc].v + tree[rc].v; // 区间和
}
void build(vector<ll>& arr, ll p, ll l, ll r)
{
tree[p] = { l,r,arr[l] };
if (l == r) return;
ll m = (l + r) >> 1;
build(arr, lc, l, m);
build(arr, rc, m + 1, r);
pushup(p);
}
void update(ll p, ll x, ll k)
{
if (tree[p].l == x && tree[p].r == x)
{
tree[p].v += k; // 单点修改为= 单点增加为+=
return;
}
ll m = (tree[p].l + tree[p].r) >> 1;
if (x <= m) update(lc, x, k);
else update(rc, x, k);
pushup(p);
}
ll query(ll p, ll l, ll r)
{
if (l <= tree[p].l && tree[p].r <= r) return tree[p].v;
ll m = (tree[p].l + tree[p].r) >> 1;
// 区间和
ll res = 0;
if (l <= m) res += query(lc, l, r);
if (r > m) res += query(rc, l, r);
return res;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q, x, y;
cin >> n >> m;
vector<ll> val(n + 1);
for (int i = 1; i <= n; i++) cin >> val[i];
SegTree st(val);
while (m--)
{
cin >> q >> x >> y;
if (q == 1) st.update(1, x, y);
else cout << st.query(1, x, y) << endl;
}
return 0;
}区间最值
如果求最小值，改成min并初始化res为无穷大即可。
C++
/* 修改pushup函数 */
tree[p].v = max(tree[lc].v, tree[rc].v); // 区间最大值
/* 修改query函数 */
// 区间最大值
ll res = -4e18;
if (l <= m) res = max(res, query(lc, l, r));
if (r > m) res = max(res, query(rc, l, r));区间与/或/异或
因为与运算只有全1才1，故初始化res为1（0000...取反~即为1111...）
或 | 和异或 ^ 初始化res为0即可。
C++
/* 修改pushup函数 */
tree[p].v = tree[lc].v & tree[rc].v; // 区间与
/* 修改query函数 */
// 区间与
ll res = ~0ull;
if (l <= m) res &= query(lc, l, r);
if (r > m) res &= query(rc, l, r);区间gcd/lcm
求lcm初始化res为1即可，需要注意取模。
C++
#include <numeric>
/* 修改pushup函数 */
tree[p].v = gcd(tree[lc].v, tree[rc].v); // 区间gcd
/* 修改query函数 */
// 区间gcd
ll res = 0;
if (l <= m) res = gcd(res, query(lc, l, r));
if (r > m) res = gcd(res, query(rc, l, r));区间最大字段和
由于最大子段和结果不独立（即既能来自左半、来自右半，也可能来自中间），我们需要增加标记特殊处理来自中间的情况。
题目：P4513 小白逛公园（https://www.luogu.com.cn/problem/P4513）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#define lc p<<1
#define rc p<<1|1
using namespace std;
using ll = long long;
struct SegTree
{
struct node
{
ll l, r, sum, mx, lmx, rmx;
};
vector<node> tree;
SegTree(vector<ll>& arr)
{
tree.resize(4 * arr.size());
build(arr, 1, 1, arr.size() - 1);
}
void pushup(node& p, const node& l, const node& r)
{
p.sum = l.sum + r.sum;
p.lmx = max(l.lmx, l.sum + r.lmx);
p.rmx = max(r.rmx, r.sum + l.rmx);
p.mx = max({ l.mx,r.mx,l.rmx + r.lmx });
}
void build(vector<ll>& arr, ll p, ll l, ll r)
{
tree[p] = { l,r,arr[l],arr[l],arr[l],arr[l] };
if (l == r) return;
ll m = (l + r) >> 1;
build(arr, lc, l, m);
build(arr, rc, m + 1, r);
pushup(tree[p], tree[lc], tree[rc]);
}
void update(ll p, ll x, ll k)
{
if (tree[p].l == x && tree[p].r == x)
{
tree[p] = { x,x,k,k,k,k };
return;
}
ll m = (tree[p].l + tree[p].r) >> 1;
if (x <= m) update(lc, x, k);
else update(rc, x, k);
pushup(tree[p], tree[lc], tree[rc]);
}
node query(ll p, ll l, ll r)
{
if (l <= tree[p].l && tree[p].r <= r) return tree[p];
ll m = (tree[p].l + tree[p].r) >> 1;
if (r <= m) return query(lc, l, r);
if (l > m) return query(rc, l, r);
node res;
pushup(res, query(lc, l, r), query(rc, l, r));
return res;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q, x, y;
cin >> n >> m;
vector<ll> val(n + 1);
for (int i = 1; i <= n; i++) cin >> val[i];
SegTree st(val);
while (m--)
{
cin >> q >> x >> y;
if (q == 1)
{
if (x > y) swap(x, y);
cout << st.query(1, x, y).mx << endl;
}
else st.update(1, x, y);
}
return 0;
}区间修改(懒标记)
直接修改是 O(n) 的，故需要引入一个tag记录修改，需要时再向下传递。
题目：P3372 【模板】线段树 1（https://www.luogu.com.cn/problem/P3372）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#define lc p<<1
#define rc p<<1|1
using namespace std;
using ll = long long;
struct SegTree
{
struct node
{
ll l, r, v, tag;
};
vector<node> tree;
SegTree(vector<ll>& arr)
{
tree.resize(4 * arr.size());
build(arr, 1, 1, arr.size() - 1);
}
void pushup(ll p)
{
tree[p].v = tree[lc].v + tree[rc].v; // 区间和
}
void pushdown(ll p)
{
if (tree[p].tag)
{
// 单点修改为= 单点增加为+=
tree[lc].v += (tree[lc].r - tree[lc].l + 1) * tree[p].tag;
tree[rc].v += (tree[rc].r - tree[rc].l + 1) * tree[p].tag;
tree[lc].tag += tree[p].tag;
tree[rc].tag += tree[p].tag;
tree[p].tag = 0;
}
}
void build(vector<ll>& arr, ll p, ll l, ll r)
{
tree[p] = { l,r,arr[l] };
if (l == r) return;
ll m = (l + r) >> 1;
build(arr, lc, l, m);
build(arr, rc, m + 1, r);
pushup(p);
}
void update(ll p, ll l, ll r, ll k)
{
if (l <= tree[p].l && tree[p].r <= r)
{
// 单点修改为= 单点增加为+=
tree[p].v += (tree[p].r - tree[p].l + 1) * k;
tree[p].tag += k;
return;
}
ll m = (tree[p].l + tree[p].r) >> 1;
pushdown(p);
if (l <= m) update(lc, l, r, k);
if (r > m) update(rc, l, r, k);
pushup(p);
}
ll query(ll p, ll l, ll r)
{
if (l <= tree[p].l && tree[p].r <= r) return tree[p].v;
ll m = (tree[p].l + tree[p].r) >> 1;
pushdown(p);
// 区间和
ll res = 0;
if (l <= m) res += query(lc, l, r);
if (r > m) res += query(rc, l, r);
return res;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
ll x, y, k;
cin >> n >> m;
vector<ll> val(n + 1);
for (int i = 1; i <= n; i++) cin >> val[i];
SegTree st(val);
while (m--)
{
cin >> q >> x >> y;
if (q == 1)
{
cin >> k;
st.update(1, x, y, k);
}
else cout << st.query(1, x, y) << endl;
}
return 0;
}区间最值
如果求最小值，改成min并初始化res为无穷大即可。
C++
/* 修改pushup函数 */
tree[p].v = max(tree[lc].v, tree[rc].v); // 区间最大值
/* 修改pushdown函数 */
// 单点修改为= 单点增加为+=
tree[lc].v += tree[p].tag;
tree[rc].v += tree[p].tag;
tree[lc].tag += tree[p].tag;
tree[rc].tag += tree[p].tag;
tree[p].tag = 0;
/* 修改update函数 */
// 单点修改为= 单点增加为+=
tree[p].v += k;
tree[p].tag += k;
/* 修改query函数 */
// 区间最大值
ll res = -4e18;
if (l <= m) res = max(res, query(lc, l, r));
if (r > m) res = max(res, query(rc, l, r));区间乘法
这里是支持区间乘以一个数 k，查询区间和。注意懒标记tag默认为1
C++
constexpr int MOD = 1e9 + 7;
struct node
{
ll l, r, v, tag = 1;
};
/* 修改pushup函数 */
tree[p].v = (tree[lc].v + tree[rc].v) % MOD; // 区间求和
/* 修改pushdown函数 */
tree[lc].v = (tree[lc].v * tree[p].tag) % MOD;
tree[rc].v = (tree[rc].v * tree[p].tag) % MOD;
tree[lc].tag = (tree[lc].tag * tree[p].tag) % MOD;
tree[rc].tag = (tree[rc].tag * tree[p].tag) % MOD;
tree[p].tag = 1;
/* 修改update函数 */
tree[p].v = (tree[p].v * k) % MOD;
tree[p].tag = (tree[p].tag * k) % MOD;
/* 修改query函数 */
// 区间求和
ll res = 0;
if (l <= m) res = (res + query(lc, l, r)) % MOD;
if (r > m) res = (res + query(rc, l, r)) % MOD;区间与/或/异或
以区间异或修改+查询区间异或和为例。
C++
/* 修改pushup函数 */
tree[p].v = tree[lc].v ^ tree[rc].v; // 区间异或
/* 修改pushdown函数 */
// 区间异或
ll len_l = tree[lc].r - tree[lc].l + 1;
ll len_r = tree[rc].r - tree[rc].l + 1;
if (len_l & 1) tree[lc].v ^= tree[p].tag;
if (len_r & 1) tree[rc].v ^= tree[p].tag;
tree[lc].tag ^= tree[p].tag;
tree[rc].tag ^= tree[p].tag;
tree[p].tag = 0;
/* 修改update函数 */
// 区间异或
ll len = tree[p].r - tree[p].l + 1;
if (len & 1) tree[p].v ^= k;
tree[p].tag ^= k;
/* 修改query函数 */
// 区间异或
ll res = 0;
if (l <= m) res ^= query(lc, l, r);
if (r > m) res ^= query(rc, l, r);区间gcd
由于gcd修改前后没有数学方式转移，故无法直接打懒标记维护。
（e.g.：gcd(2, 4)=2, 将区间加2得 gcd(4, 6)=2, 将区间加1得 gcd(3, 5)=1）
虽然不能直接维护，我们可以利用gcd的欧几里得算法（辗转相除法）性质转换为单点修改。
gcd(a1, a2, a3, …, an) = gcd(a1 , a2 − a1, a3 − a2, …, an − an−1)
所以问题就转化为了用线段树维护差分序列的区间和与区间gcd。
题目：P10463 Interval GCD（https://www.luogu.com.cn/problem/P10463）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define lc p<<1
#define rc p<<1|1
using namespace std;
using ll = long long;
struct SegTree
{
struct node
{
ll l, r, sum = 0, gcd = 0;
};
vector<node> tree;
SegTree(vector<ll>& arr)
{
tree.resize(4 * arr.size());
build(arr, 1, 1, arr.size() - 1);
}
void pushup(node& p, const node& l, const node& r)
{
p.sum = l.sum + r.sum;
p.gcd = gcd(l.gcd, r.gcd);
}
void build(vector<ll>& arr, ll p, ll l, ll r)
{
tree[p] = { l,r,arr[l],arr[l] };
if (l == r) return;
ll m = (l + r) >> 1;
build(arr, lc, l, m);
build(arr, rc, m + 1, r);
pushup(tree[p], tree[lc], tree[rc]);
}
void update(ll p, ll x, ll k)
{
if (tree[p].l == x && tree[p].r == x)
{
tree[p].sum += k;
tree[p].gcd += k;
return;
}
ll m = (tree[p].l + tree[p].r) >> 1;
if (x <= m) update(lc, x, k);
else update(rc, x, k);
pushup(tree[p], tree[lc], tree[rc]);
}
node query(ll p, ll l, ll r)
{
if (l <= tree[p].l && tree[p].r <= r) return tree[p];
ll m = (tree[p].l + tree[p].r) >> 1;
if (r <= m) return query(lc, l, r);
if (l > m) return query(rc, l, r);
node res;
pushup(res, query(lc, l, r), query(rc, l, r));
return res;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, x, y;
ll k;
char q;
cin >> n >> m;
vector<ll> val(n + 1), adj(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> val[i];
adj[i] = val[i] - val[i - 1];
}
SegTree st(adj);
while (m--)
{
cin >> q >> x >> y;
if (q == 'C')
{
cin >> k;
st.update(1, x, k);
if (y + 1 <= n) st.update(1, y + 1, -k);
}
else
{
SegTree::node l, r;
l = st.query(1, 1, x);
if (x + 1 <= y) r = st.query(1, x + 1, y);
cout << gcd(l.sum, r.gcd) << endl;
}
}
return 0;
}区间乘法+区间加法
题目：P3373 【模板】线段树 2（https://www.luogu.com.cn/problem/P3373）
动态开点
题目：P13825 【模板】线段树 1.5（https://www.luogu.com.cn/problem/P13825）
分块
莫队算法
莫队被称为“优雅的暴力”，本质是一种把所有查询排序后暴力转移的离线算法。
普通莫队
利用分块排序查询并在查询间转移，可以实现 O(n sqrt(n)) 的时间复杂度。
题目：P2709 【模板】莫队 / 小B的询问（https://www.luogu.com.cn/problem/P2709）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> arr, cnt;
int BLK, sum = 0;
struct query
{
int l, r, id;
bool operator < (const query& q) const {
if (l / BLK == q.l / BLK) return r < q.r;
return l < q.l;
}
};
void add(int x)
{
sum -= cnt[x] * cnt[x];
cnt[x]++;
sum += cnt[x] * cnt[x];
}
void del(int x)
{
sum -= cnt[x] * cnt[x];
cnt[x]--;
sum += cnt[x] * cnt[x];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
BLK = sqrt(n);
cnt.resize(k + 1);
arr.resize(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
vector<query> q(m);
vector<int> ans(m);
for (int i = 0; i < m; i++)
{
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q.begin(), q.end());
int l = 1, r = 0;
for (auto& i : q)
{
while (l > i.l) add(arr[--l]);
while (r < i.r) add(arr[++r]);
while (l < i.l) del(arr[l++]);
while (r > i.r) del(arr[r--]);
ans[i.id] = sum;
}
for (auto& i : ans) cout << i << "\n";
return 0;
}我们还可以进一步优化排序，降低常数。
C++
struct query
{
int l, r, id;
bool operator < (const query& q) const {
if (l / BLK == q.l / BLK)
{
if ((l / BLK) & 1) return r < q.r;
else return r > q.r;
}
return l < q.l;
}
};带修莫队
想让莫队支持修改，可以再加上一维时间t。并在时间之间转移，时间复杂度O(N5/3)。
题目：P1903 【模板】带修莫队 / [国家集训队] 数颜色（https://www.luogu.com.cn/problem/P1903）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using pii = pair<int, int>;
vector<int> arr, cnt(1e6 + 3);
int BLK, sum = 0;
struct query
{
int l, r, t, id;
bool operator < (const query& q) const {
if (l / BLK != q.l / BLK) return l < q.l;
else if (r / BLK != q.r / BLK) return r < q.r;
else return t < q.t;
}
};
void add(int x)
{
if (!cnt[x]) sum++;
cnt[x]++;
}
void del(int x)
{
cnt[x]--;
if (!cnt[x]) sum--;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m, x, y;
char typ;
cin >> n >> m;
BLK = pow(n, 2.0 / 3.0);
arr.resize(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
vector<query> q;
vector<pii> edit(1);
vector<int> ans;
int id = 0, tim = 0;
while (m--)
{
cin >> typ >> x >> y;
if (typ == 'Q')
{
q.emplace_back(query{ x, y, tim, id++ });
}
else
{
edit.emplace_back(x, y);
tim++;
}
}
ans.resize(id);
sort(q.begin(), q.end());
int l = 1, r = 0, ct = 0;
for (auto& i : q)
{
while (l > i.l) add(arr[--l]);
while (r < i.r) add(arr[++r]);
while (l < i.l) del(arr[l++]);
while (r > i.r) del(arr[r--]);
while (ct < i.t)
{
int pos = edit[++ct].first;
if (pos >= l && pos <= r)
{
del(arr[pos]);
add(edit[ct].second);
}
swap(arr[pos], edit[ct].second);
}
while (ct > i.t)
{
int pos = edit[ct].first;
if (pos >= l && pos <= r)
{
del(arr[pos]);
add(edit[ct].second);
}
swap(arr[pos], edit[ct--].second);
}
ans[i.id] = sum;
}
for (auto& i : ans) cout << i << "\n";
return 0;
}目前有关区间查询类问题就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。
版权声明：
作者：Toms Project
链接：https://blog.projectoms.com/pages/1750.html
来源：Toms Project 官方博客
文章版权归作者所有，未经允许请勿转载。
THE END
二维码
打赏
文章目录
关闭
共有 0 条评论