C++ 算法技巧 — 下标技巧 (Indexing Techniques)

章节概述

下标技巧是算法竞赛中最基础也最灵活的技巧之一，涉及数组下标的映射、转换、偏移和压缩，
直接影响程序的正确性和效率。

核心原理

1. 0-based vs 1-based

场景	推荐	原因
前缀和、差分、DP	1-based	pre[0]=0 自然成立，避免 i-1<0 边界判断
原始输入、STL	0-based	STL 统一使用 0-based
混合使用	注意转换	a_1based[i] = input[i-1]

2. 离散化 (坐标压缩)

当数据范围很大（如 10^9）但实际使用的值很少（如 10^5），将原值映射到紧凑范围 [1, m]：

步骤: 排序 → 去重 → 二分查找映射
m = unique(tmp, tmp + n) - tmp
a[i] = lower_bound(tmp, tmp + m, a[i]) - tmp + 1

保序映射，时间复杂度 O(n log n)。

3. 负数下标处理

const int OFFSET = 1005;
int cnt[2010];
int& at(int idx) { return cnt[idx + OFFSET]; }
// 将 [-1000, 1000] 映射到 [5, 2005]

关键数据结构

E_容器_Container — vector 基于 0-based 索引

下标偏移

在动态规划和前缀和问题中，常用 1-based 下标避免边界判断。

// 1-based: 自然避免了 i-1=0 的越界问题
int dp[1005][1005] = {0};
for (int i = 1; i <= n; i++)
 for (int j = 1; j <= m; j++)
 dp[i][j] = dp[i-1][j] + dp[i][j-1] + a[i][j];

下标映射 (离散化)

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005], tmp[100005];
 
int main() {
 int n;
 cin >> n;
 for (int i = 0; i < n; i++) {
 cin >> a[i];
 tmp[i] = a[i];
 }
 sort(tmp, tmp + n);
 int m = unique(tmp, tmp + n) - tmp;
 for (int i = 0; i < n; i++)
 a[i] = lower_bound(tmp, tmp + m, a[i]) - tmp + 1;
 return 0;
}

P1047 [NOIP2005 普及组] 校门外的树

题目: 长度为 L 的马路上有树，挖掉 M 个区间的树，求剩余数量。

#include <iostream>
using namespace std;
bool tree[10005];
 
int main() {
 int L, M;
 cin >> L >> M;
 for (int i = 0; i <= L; i++) tree[i] = true;
 while (M--) {
 int u, v;
 cin >> u >> v;
 for (int i = u; i <= v; i++)
 tree[i] = false;
 }
 int cnt = 0;
 for (int i = 0; i <= L; i++)
 if (tree[i]) cnt++;
 cout << cnt << endl;
 return 0;
}

P1957 口算练习题

题目: 给出一系列算式，判断是加法还是减法运算，输出竖式格式。

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
int main() {
 int n;
 cin >> n;
 while (n--) {
 string s, a, b;
 char op;
 cin >> s;
 if (s[0] >= 'a' && s[0] <= 'z') {
 op = s[0];
 cin >> a >> b;
 } else {
 a = s;
 cin >> b;
 }
 int len = max(a.size(), b.size()) + 1;
 cout << a << endl;
 cout << b << endl;
 for (int i = 0; i < len; i++) cout << '-';
 cout << endl;
 }
 return 0;
}

RootStack

探索

C++ 算法技巧 — 下标技巧 (Indexing Techniques)

章节概述

核心原理

关键数据结构

下标偏移

下标映射 (离散化)

P1047 [NOIP2005 普及组] 校门外的树

P1957 口算练习题

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接