高效求区间操作

对于区间l,r，高效查询它的区间和，差或者异或，我最先接触的算法是前缀和与差分，通过预处理，o(1)查询区间问题，差分通过构造差分数组再求前缀实现区间修改，这种算法思路很简单理解也不困难，这里就不展示代码了

然后是树状数组，时间复杂度是log n,通过把一个区间的数分成若干2的n次方的段，可以实现单点修改，区间查询的效果，代码如下：

其中lowbit(x) 取下标最低位的 1，树状数组节点保存一段固定长度的和。更新时向上影响所有包含该位置的区间；查询时不断拆掉最低位，组合成前缀和。

• 复杂度：单点更新、前缀和均 O(log n)。

• 注意：下标必须从 1 开始；区间和为 sum(r) - sum(l - 1)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x&(-x))
const int N = 1e5 + 10;
int c[N];  
int getsum(int x)
{
	int ans=0;
	for (int i=x;i>=1;i-=lowbit(i))
	{
		ans+=c[i];
	}
	return ans;
}
void updata(int x,int v)
{
	for (int i=x;i<=N;i+=lowbit(i))
	{
		c[i]+=v;
	}
}
void solve()
{

}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--)
{
solve();
}
return 0;
}

但是如果要求区间最大/小值，这个时候就需要用到st表，对于代码的理解，st[i][j] 表示从 i 开始、长度为 2^j 的区间最大值。查询时用两个长度相同、允许重叠的块覆盖目标区间。最大值、最小值、GCD 这类幂等运算都适用。

• 复杂度：预处理 O(n log n)，每次查询 O(1)。

• 注意：只适合静态数组；原模板内层边界应使用 n，不能写成数组上限 N。

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
using pii=pair<int,int>;
const int mod=1e9+7;
const int N=1e5+10;
const int M=22;
#define endl '\n'
#define lowbit(x) (x&(-x))
#define vc vector<int>

inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x10+ch-48;ch=getchar();}
return xf;
}
int n,m;
int st[N][M];
int a[N];
void pre()
{
for (int i=1;i<=n;i++) st[i][0]=a[i];
for (int j=1;j<M;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]);
}
}
}
int query(int l,int r)
{
int ans=-1e9;
int len=__lg(r-l+1);
ans=max(st[l][len],st[r-(1<<len)+1][len]);
return ans;
}
void solve()
{
n = read(), m = read();
for (int i=1;i<=n;i++)
{
a[i]=read();
}
pre();
while(m--)
{
int l = read();
int r = read();
cout<<query(l,r)<<endl;
}
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--)
{
solve();
}
return 0;
}

上面两种做法都是静态求值，对于动态修改区间查询的问题，就需要用到一种高级的数据结构，线段树，这里只介绍线段树的代码，后面会单独开一篇介绍

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
using pii=pair<int,int>;
const int mod=1e9+7;
//const int maxn=1e6+5;
#define lowbit(x) (x&(-x))
#define vc vector<int>
const int INI_MIN=-1e9;
const int INI_MAX=1e9;

struct node
{
int data,lazy=0;
};

//建树
void build(const vector<int> &data, vector<node> &tree, int t,int left,int right)
{
if (left==right)
{
tree[t].data=data[left];
return;
}
int mid=(right+left)/2;
build(data,tree,2t,left,mid); //左子树
build(data,tree,2t+1,mid+1,right); //右子树
tree[t].data = max(tree[2t].data,tree[2t+1].data); //更新当前的最小值
}

//查找懒标记
void pushdown(vector<node> &tree,int t)
{
if (tree[t].lazy!=0)
{
// 更新左子树
tree[2t].data+=tree[t].lazy;
tree[2t].lazy+=tree[t].lazy;
//更新右子树
tree[2t+1].data+=tree[t].lazy;
tree[2t+1].lazy+=tree[t].lazy;
//清空当前节点的懒标记
tree[t].lazy=0;
}
}

//区间查询
int query(vector<node> &tree,int t,int left,int right,int ql,int qr)
{
if (ql>right || qr<left)
{
return INI_MIN;
}
if (ql<=left && qr>=right)
{
return tree[t].data;
}

int mid = (left+right)/2;
pushdown(tree,t);
int leftmax = query(tree,2t,left,mid,ql,qr);
int rightmax = query(tree,2t+1,mid+1,right,ql,qr);
return max(leftmax,rightmax);

}

//单点修改
void updata(vector<node> &tree, int t,int left, int right,int idx,int value)
{
if (left==right)
{
tree[t].data = value;
tree[t].lazy = 0; //找到目标点更新值
return ;
}

int mid=(left+right)/2;
pushdown(tree,t);

if (idx<=mid)  //更新左子树
{
updata(tree,2t,left,mid,idx,value);
}
else //更新右子树
{
updata(tree,2t+1,mid+1,right,idx,value);
}
tree[t].data = max(tree[2t].data,tree[2t+1].data);

}

// 区间更新
void updatarange(vector<node> &tree, int t,int left,int right,int ql,int qr,int value)
{
if (ql > right || qr < left)
{
return ; //区间无交集
}
if (ql <= left && qr >= right)
{
tree[t].data+=value;
tree[t].lazy+=value;
return ;
}
int mid=(left+right)/2;
pushdown(tree,t);
updatarange(tree,2t,left,mid,ql,qr,value);
updatarange(tree,2t+1,mid+1,right,ql,qr,value);
tree[t].data = max(tree[2t].data,tree[2t+1].data);
}

void solve()
{
int n,m;
cin>>n>>m;
vector<int>data(n+1);
vector<node>tree((n+1)4);

for(int i=1;i<=n;i++)
cin>>data[i];
build(data,tree,1,1,n);
while (m--)
{
int op;
cin>>op;
if (op==1)
{
int x,y,z;
cin>>x>>y>>z;
updatarange(tree,1,1,n,x,y,z);
}
else
{
int x,y;
cin>>x>>y;
cout<<query(tree,1,1,n,x,y)<<endl;
}
}

}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--)
{
solve();
}
return 0;
}

最后我新学到的一种处理暴力查询区间问题的优化算法，莫队分块处理，可以离线处理大量区间查询，把O(n²)优化为O(nsqrt(n))

莫队：把所有询问重新排序，用两个指针 l、r，不断左右移动，增量维护当前区间的答案。

 add(x) ：把位置x加入当前区间，更新答案

​ del(x) ：把位置x移出当前区间，更新答案

通过排序，让 l、r 指针总共移动次数控制在 O(n\sqrt n)。

分块排序规则

1. 将数组分成块，块大小一般取 block = sqrt n。

2. 对每个询问  (L,R,id) ：

- 按  L / block （所属块）第一关键字排序；

- 如果块编号是奇数：按R升序；偶数块按R降序 → 奇偶优化（减少r来回跑，竞赛必加）

3. 最后要按原来询问的 id 把答案输出，因为询问被打乱顺序。

while(l > q[i].L) add(--l);
while(r < q[i].R) add(++r);
while(l < q[i].L) del(l++);
while(r > q[i].R) del(r--);

‍