一些概念
- 在线操作：每读入一个操作方式，就进行一次修改或者输出结果。
- 离线操作：将所有操作先全部读入存起来，进行处理后再进行修改或者输出结果。
我们很多时候，对线段树或者树状数组都是进行在线操作的，边读入操作边修改。但是用树状数组来解决一些题目时，得依赖离线操作来限制在树状数组内信息的范围。不理解这句话不要紧，这里有两道很好的例题可以用离线操作解决。
题目一：换个角度思考
题意简述
题目给出一个长为 (n) 的序列（均小于 (10^5)），无需修改，只要 (m) 次查询：查询时一个三元组 (<l,r,num>) ，意在询问 ([l,r]) 区间内小于或等于 (num) 的个数。数据保证 (n leq 10^5 ,m leq 10^5,) (1 leq l leq r leq n,num leq 10^5) 。
离线分析
考虑简单情况，对给定序列询问小于等于某个数的数量，可以用树状数组轻松解决。但是现在要限定在某个区间的内的查询，用树状数组在线操作是很难实现的（什么主席树、莫队的我还不会┭┮﹏┭┮）。那我们考虑一下离线操作吧，这里提供两种离线思路和代码。
按查询区间端点离线
也许你已经想到了，如果查询在 ([l,r]) 区间上小于等于 (num) 的数目，其实就等于在 ([1,r]) 区间上小于等于 (num) 的数目减去在 ([1,l-1]) 区间上小于等于 (num) 的数目。那么，我们可以将所有查询的端点 (pos) 从小到大排序，然后在树状数组中依次加入原序列，限定在树状数组中的数一定是在 ([1,pos]) 区间内的。为了区分左右端点，还得做一个标记 (kind)，左端点是 (-1) ，右端点是 (1)，这样合并答案的时候就可以实现右边减左边的操作。因为是离线查询,要存每一个端点对应哪次询问的答案，和上面的 (kind) 相乘即可。
(Code:)
#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
const int maxn = 1e5+9;
int n,m,t[maxn],num[maxn],ans[maxn],range;
struct Question{
//pos表示查询的区间为[1,pos],id 用来定位查询的序号,num是要比较的值，kind=-1是左端点，kind=1为右端点
int pos,id,num,kind;
bool operator < (const Question &y)const{
return pos<y.pos;
}
}q[maxn<<1];
void update(int now){
while(now <= range){
t[now]++;
now += lowbit(now);
}
}
int query(int now){
int an = 0;
while(now){
an+=t[now];
now -= lowbit(now);
}return an;
}
int main(){
speedUp_cin_cout
cin>>n>>m;
For(i,1,n) cin>>num[i],range = max(range,num[i]);
//一次操作根据端点拆分成两项
int lef,rig;
For(i,1,m) {
lef = (i << 1)-1;
rig = i << 1;
cin >> q[lef].pos >> q[rig].pos >> q[lef].num;
q[rig].num = q[lef].num;
q[lef].pos --; //注意左端点要减1，因为查询的是[l,r]区间上的数
q[rig].id = q[lef].id = i;
q[lef].kind = -1, q[rig].kind = 1;
}
sort(q+1,q+2*m+1);
//i是原数组下标，j是离线的查询数组下标
for(int i = 1,j = 1;j <= 2*m;j++){
//当原数组下标小于等于当前查询的位置，就继续往线段树里塞元素
while(i <= q[j].pos && i <= n) update(num[i++]);
ans[q[j].id] += query(q[j].num) * q[j].kind;
}
For(i,1,m) cout<<ans[i]<<endl;//最后按原来顺序输出查询答案
return 0;
}
代码中定义了一个结构体存查询状态。记得左端点要减一。同时循环那里要小心，经常容易 (WA) ，写法虽然很多，但是这种写法是最短的而且不容易错的，比较推荐。
按查询数字大小离线
还有一种方法是按照查询的数字排序，然后把原序列也给排序了。设原序列数字为 (a_i) ，查询数字为 (num_j) 。把比 (num_j) 小的 (a_i) 加入线段树，然后查询在区间 ([l,r]) 的数有多少个就行了。注意加入线段树的是 (a_i) 的下标 (i) ，和上面的做法不一样。这样由于 (num) 是升序的，前面比 (a_i) 大的数，后面一定也比 (a_i) 大，所以正确性可以得到保证。因为还要保存原序列的下标，所以给原序列也定义了一个结构体。
(Code:)
#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
const int maxn = 1e5+9;
int n,m,t[maxn],ans[maxn];
struct Question{
//[l,r]是查询区间,num是要比较的值
int l,r,num,id;
bool operator < (const Question &y)const{
return num<y.num;
}
}q[maxn];
struct Data{
//数据，位置
int num, pos;
bool operator < (const Data &y)const{
return num<y.num;
}
}a[maxn];
void update(int now){
while(now <= n){
t[now]++;
now += lowbit(now);
}
}
int query(int now){
int an = 0;
while(now){
an+=t[now];
now -= lowbit(now);
}return an;
}
int main(){
speedUp_cin_cout
cin>>n>>m;
For(i,1,n) {
cin>>a[i].num;
a[i].pos = i;
}
For(i,1,m) {
cin>>q[i].l>>q[i].r>>q[i].num;
q[i].id = i;
}
sort(q+1,q+1+m);
sort(a+1,a+1+n);
//i是原数组下标，j是查询下标
for(int i = 1,j = 1; j <= m;j++){
while(a[i].num <= q[j].num && i <= n) update(a[i++].pos);
ans[q[j].id] = query(q[j].r) - query(q[j].l - 1);
}
For(i,1,m) cout<<ans[i]<<endl;
return 0;
}
两种方法都是可以的，随心选择吧，如果有更好的离线算法也可以和我讨论。我其实只想出了第一种按端点的离线。如这道题的题目一样，我们换个角度思考，树状数组模板又可以轻松套上了。
题目二：配对统计
题意简述
给定 (n) 个数 (a_{1}, cdots, a_{n})，定义好的配对((x, y))：若对于所有的 $i=1,2, cdots, n, $ 满足 (left|a_{x}-a_{y} ight| leq) (left|a_{x}-a_{i} ight|(i eq x),) 则称 ((x, y)) 为一组好的配对。然后询问 (m) 次，每次询问区间 ([l, r]) 中含有多少组好的配对,要求 (l leq x, y leq r ext { 且 } x eq y)。数据保证 (a_i) 互不相等，且 (1leq a_{i} leq 10^{9}) , (n leq 3 imes 10^5) 。最后输出一个值 (sum_{i=1}^{m} A n s_{i} imes i，Ans_i) 为第 (i) 次查询结果。
离线分析
这道题和上一道题有类似的地方，都是没有区间修改，但是有比较难在线处理的区间查询。我们考虑进行离线操作。首先由定义可知，对于好的配对 ((x, y),) 一定在排成有序时 (a_{x}) 和 (a_{y}) 相邻，我们可以 (mathcal O(nlogn)) 预处理出所有配对，并放入一个结构体数组中。然后我们为了让加入树状数组里的数据来源限定在一定的范围内，就得对查询的区间进行一通排序，将区间右端点小的放在前面。对配对结构体数组也是这样排序（排序的方式并不唯一，写法改一下而已，但是配对数组的排序要和查询数组排序一致）。
这样，对于某个查询 ([l,r]) ，把所有右端点小于等于 (r) 的配对的左端点都放进树状数组里头，然后查询大于 (l-1) 的端点有多少个，就说明有几个配对被包含在区间 ([l,r]) 了。以此类推，因为后面查询的 (r) 一定大于或等于前面的 (r) ，所以树状数组里的数据始终在 ([1,r]) 这个范围里，查询就能保证正确性了。
(Code:)
#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 3e5+9;
struct Num{
int num,pos;
bool operator < (const Num &y) const{
return num < y.num;
}
}num[maxn];
//配对和查询结构体数组，实际上配对用不到id变量，id记录的是查询的次序
struct node{
int l,r,id;
bool operator < (const node &y)const{
return r < y.r; //注意是按右端点小的排前面
}
}p[maxn<<1],q[maxn]; //p中存在原序列中所有好的配对，q存每条查询
ll t[maxn],n,m,ans,cnt; //注意答案可能会爆int，cnt统计总配对数
void update(int now){
while(now <= n){
t[now]++;
now += lowbit(now);
}
}
ll query(int now){
ll an = 0;
while(now){
an += t[now];
now -= lowbit(now);
}return an;
}
//增添配对函数
void Add(int now){
ll d1 = abs(num[now].num - num[now-1].num); //与左边的差距
ll d2 = abs(num[now].num - num[now+1].num); //与右边的差距
//如果左右相等，说明x=now时有两个配对
if(d1 == d2) {
p[++cnt].l = min(num[now].pos, num[now - 1].pos); //左端点取小的
p[cnt].r = max(num[now].pos, num[now - 1].pos); //右端点取大的
p[++cnt].l = min(num[now].pos, num[now + 1].pos);
p[cnt].r = max(num[now].pos, num[now + 1].pos);
}else if(d1 < d2){
//配对在左边
p[++cnt].l = min(num[now].pos, num[now - 1].pos);
p[cnt].r = max(num[now].pos, num[now - 1].pos);
}else{
//配对在右边
p[++cnt].l = min(num[now].pos, num[now + 1].pos);
p[cnt].r = max(num[now].pos, num[now + 1].pos);
}
}
int main(){
speedUp_cin_cout //读写优化
cin>>n>>m;
num[0].num = num[n+1].num = -0x3f3f3f3f;//这里是为了不用特判端点，因为配对肯定取不到0 和 n+1
For(i,1,n) cin>>num[i].num,num[i].pos = i;
sort(num+1,num+1+n); //先排序
For(i,1,n) Add(i); //后找配对，加入好的配对数组p中
sort(p+1,p+1+cnt);
For(i,1,m) cin >> q[i].l >> q[i].r, q[i].id = i;//读入查询
sort(q + 1, q + 1 + m);
//i是已配对数组p的下标，j是查询数组q的下标，注意不要写错
for(int i = 1,j = 1;j <= m;j++){
while(p[i].r <= q[j].r && i <= cnt) update(p[i++].l);
//如果配对的区间仍在[1 , q[j].r]范围内，就把它的左端点下标加进树状数组
ans += (query(q[j].r) - query(q[j].l - 1)) * q[j].id;
//查询[q[j].l , q[j].r]所有配对的数目
//也可以这样写 ans += (query(n) - query(q[j].l - 1)) * q[j].id;
//因为树状数组里的数据肯定是在[1 , q[j].r]范围内的，这样写没错也证明了这一点。
}
cout<<ans;
return 0;
}
这样做的实质其实是为了让每一个查询 ([l,r])，都在所有包含在 ([1,r]) 内的配对全部加进树状数组的前提下进行（断句困难）。这也是离线操作比较妙的地方。还有不清楚的欢迎来讨论(o゜▽゜)o☆