对于区间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,2*t,left,mid,ql,qr);
int rightmax = query(tree,2*t+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&lt;=mid)  //更新左子树
{
    updata(tree,2*t,left,mid,idx,value);
}
else //更新右子树
{
    updata(tree,2*t+1,mid+1,right,idx,value);
}
tree[t].data = max(tree[2*t].data,tree[2*t+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&lt;=n;i++) 
    cin&gt;&gt;data[i];
build(data,tree,1,1,n);
while (m--)
{
    int op;
    cin&gt;&gt;op;
    if (op==1)
    {
        int x,y,z;
        cin&gt;&gt;x&gt;&gt;y&gt;&gt;z;
        updatarange(tree,1,1,n,x,y,z);
    }
    else
    {
        int x,y;
        cin&gt;&gt;x&gt;&gt;y;
        cout&lt;&lt;query(tree,1,1,n,x,y)&lt;&lt;endl;
    }
}

}

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

最后我新学到的一种处理暴力查询区间问题的优化算法，莫队分块处理，可以离线处理大量区间查询，把O(n²)优化为O(n*sqrt(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--);

‍

‍

沐晴

字符串总结

一起同行的回忆

算法竞赛心路

夜间模式