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]

关键数据结构

A_容器_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 口算练习题

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接