0 Basic 位运算基础 1# 基本操作 2a & b # 按位与：两个都是 1 才为 1 3a | b # 按位或：有一个 1 就为 1 4a ^ b # 按位异或：不同为 1，相同为 0 5~a # 按位取反 6a << n # 左移 n 位（×2^n） 7a >> n # 右移 n 位（÷2^n） 8 9# 异或的重要性质 10a ^ 0 = a # 任何数异或 0 不变 11a ^ a = 0 # 任何数异或自身为 0 12a ^ b ^ a = b # 异或可以"消除"成对出现的数 1. 只出现一次的数字 | Easy 题目：非空数组，除一个元素只出现一次外，其余元素均出现两次。找出那个数。要求 O(n) 时间、O(1) 空间 思路分析： 朴素做法：哈希表/Counter统计每个数字出现次数，空间为O(n) 位运算异或：a ^ 0 = a, a ^ a = 0, a ^ b ^ a = b 踩坑记录： ...
0 Prefix Sum Basic 0.1 前缀和定义（1-indexed） 数列前n项和： 1-indexed: $$\text{prefixSum}[i] = \sum_{j=1}^{i} a[j] = a[i] = a[1] + a[2] + \cdots + a[i]$$ 0-indexed: $$\text{prefixSum}[i] = \sum_{j=0}^{i-1} a[j] = a[i]= a[0] + a[1] + \cdots + a[i-1]$$ 前缀和分为两类： 类型 预处理 查询 一维前缀和 $O(n)$ $O(1)$ 二维前缀和 $O(nm)$ $O(1)$ 区间和公式： 1-indexed：$\text{sum(l, r) = prefixSum[r] - prefixSum[l - 1]}$ 0-indexed：$\text{sum(l, r) = prefixSum[r + 1] - prefixSum[l]}$ 适用场景: 数组不变(静态),多次查询区间和 → 前缀和 数组会被修改 → 需要树状数组 / 线段树(前缀和不适用) “子数组和满足某条件"的计数问题 → 前缀和 + 哈希表 0.1.1 一维前缀和 区间[l , r]的和：$$\text{sum}(l, r) = S[r] - S[l - 1]$$ ...