与树状数组类似，线段树也是一种用来维护区间信息的数据结构，可以在对数时间复杂度内实现更新和查询等操作。但相较于树状数组多用于前缀和查询不同，线段树的应用范围更为广泛，例如区间最值等问题，代价是需要消耗更多的存储空间。 结构对于一个长度为 7 的数组，根据该数组 nums 元素建立的线段树结构如下图所示。 每个结点存储的值为区间 nums[L ~ R] 的元素和，其中根节点对应的 L = 0, R = 6，即整个数组的元素和。然后每一层的结点将区间均分为 [L, (L + R) / 2] 和 [(L + R) / 2 + 1, R] 两部分。注意按此方式进行划分，得到的两个子区间始终满足：左右区间长度分别为 len1 和 len2，且 len1 == len2 || len1 == len2 + 1。不难得知：这样的结构构成一个完全二叉树，因此使用顺序存储将会变得很方便：根节点下标为 0；对于每个下标为 idx 的结点，其左孩子下标为 2 * idx + 1，右孩子下标为 2 * idx + 2。 构造由于叶子结点的 L 和 R 相等，其值正好为 nums[L]，而每个父结点的值为 ...

最近几个月看了不少耳机相关的内容，初步了解了一些耳机的参数指标以及选购方案，同时也给自己使用的耳机进行了一波更新换代。本文就简单盘点一下自己之前用过的和现在正在使用的耳机，内容完全基于个人的使用体验。 已退役赛睿 Arctis9x 主要是为了无线连接 xbox 而购入。买之前看了不少网上的评价，包括视频评测以及 RTINGS 网站上的测试，感觉很不错，但是这耳机并没有国行版本，而且海外版售价高达 200 美元，对我而言实在是太贵，就在淘宝花 398 购入了一副所谓的“9成新”的“洋垃圾”。 单就产品本身的素质来说，我觉得还是很不错的。尽管作为游戏耳机，但它的音乐表现依然非常出色，三频的表现十分均衡。参考 RTINGS 网站上对于 9x 的评测，其中 Neutral Sound 项评分高达 7.8 分并给出了 “satisfactory” 的评价。麦克风质量也相当不错，这根可伸缩的麦克风虽小，但却拥有优秀的收音质量和降噪能力，不过我也只是拿到手的时候测试了一下，并没有怎么使用。佩戴方面，耳机头梁采用了松紧带的设计，使得佩戴时不至于压头。耳罩不算很透气，夏天佩戴可能会比较热，但好在相对 ...

前缀和的不足前缀和是一种常见的算法思想，能够实现在常数时间复杂度下得到某个子区间内所有元素和。以一维数组 nums 为例，定义前缀和数组 preSum，preSum[i] 表示 nums 前 i 个元素的和，利用动态规划的思想，易得 preSum[i] = preSum[i - 1] + nums[i] 的递推关系，因此构造一个前缀和数组的时间复杂度为 O(n)，而查询前 i 个元素的和只需查询 preSum[i] 的值，为常数时间。 前缀和方法在数组元素不发生改变的情况下十分高效，但如果数组元素可能会发生改变，与朴素求和做法（不使用前缀和数组，而是直接遍历区间元素累计求和）相比，前缀和数组需要 O(n) 的时间来进行更新。这两种做法要么查询是 O(1)、更新是 O(n)，要么查询是 O(n)、更新是 O(1)，那有没有一种折衷的方案，使得查询和更新效率都不至于太低呢？本文将介绍的树状数组就符合这样的条件。 树状数组查询由正整数的二进制表示可知，任何一个正整数都可以拆分为为若干个不重复的 2 的幂之和。那么对于一个下标从 1 开始且长度为 n 的数组，它的任意下标 i (1 < ...

C/C++ 中有时会遇到一些位级操作，通常是一些隐式的类型转换，它们往往很难凭借高级语言层面的直觉来理解或记忆。本文旨在分析这些操作对应的汇编代码，从机器指令的角度来理解这类操作。 补码数转换为更长的无符号数int main() { short a = -12345; unsigned b = a; cout << a << " " << b << endl; // -12345 4294954951 } 首先看以上这个示例，一个短整型数据（2 字节）强制类型转换为无符号整型数据（4 字节）之后，得到的值却是一个看似毫不相关的结果。 void showBytes(unsigned char* ptr, size_t sz) { for (int i = 0; i < sz; ++i) { printf("%.2x ", ptr[i]); } printf("\n"); } 首先，为了更好地分析这类位级操作，这里编写了一个简单的字节打印函数，通过将指向 ...

在 LeetCode 刷题过程中，有时候遇到一些难以难以直接观察出来的错误，此时通常想要利用单步调试来解决，但奈何只有 LeetCode Plus 会员才可以使用其网页的调试功能。好在绝大部分本地 IDE 都具备十分强大的调试功能，我们只需要将自己的解题代码复制到本地，并编写简单的测试程序即可。但是对于二叉树相关的题，测试数据的编写显得不那么容易，本文编写了一个匹配 LeetCode 题目中的二叉树定义的类，该类包含一些基本的静态函数，能够很方便地实现二叉树的构造和二叉树的遍历。 LeetCode 二叉树的序列表示方式LeetCode 中针对二叉树的输入数据以一个层序遍历序列的形式给出。与通常我们所说的层序序列不同的是，该层序序列包含从根节点到最后一个非空结点之间的所有空结点，该空结点以 null 的标识符给出，以此保证根据此序列所构造二叉树的唯一性（单纯依靠常规的不含空结点的层序序列无法构造一棵唯一的二叉树）。以下是一个简单的例子： 输入： root = [3, 9, 20, null, null, 15, 7] 带构造与遍历的二叉树类为了方便能在本地 IDE 中直接根据输入数 ...

最近在比赛和刷题的时候经常遇到二分答案的题，但时不时会因为一些细节上的错误而浪费时间，本文旨在整理常见的二分搜索的写法、二分搜索可能会遇到的一些小问题，以及 C++ 中与二分搜索相关的库函数，以免今后再犯类似的错误。 二分搜索的写法查找某个值的下标定义函数 binarySearch(nums, target) 为搜索有序数组 nums 中是否存在 i 使得 nums[i] == target，如果是，返回 i，否则返回 -1. int binarySearch(vector<int>& nums, int target) { int low = 0, high = (int)nums.size() - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { high = mid ...

装载问题题目描述 解题代码递归回溯// goods[i]表示货物i的重量, c1,c2分别表示货船1和货船2的载重量 vector<vector<int>> optimalLoading(vector<int>& goods, int c1, int c2) { int n = goods.size(); // 货物数量 int maxSum = 0; // 当前最大载货量 // curSelection[i]表示货物i是否放入货船1中（true表示放入） vector<bool> curSelection(n, false); // optimSelection记录maxSum对应的货物存放方式 vector<bool> optimSelection; // 递归搜索函数 function<void(int, int)> dfs = [&](int sum, int idx) { if (idx == n) { // 搜索达到最大深度，得到一个解 if (sum > maxS ...

活动安排问题题目描述 解题代码vector<bool> greedySelector(vector<vector<int>>& intervals) { int n = intervals.size(); // 将活动区间按结束时间的从小到大排序 auto cmp = [](vector<int>& interval1, vector<int>& interval2) { return interval1[1] < interval2[1]; }; sort(intervals.begin(), intervals.end(), cmp); vector<bool> res(n, false); // 结束时间最早的活动必定位于某个最优解之中 int minStart = intervals[0][1]; res[0] = true; for (int i = 1; i < n; ++i) ...

矩阵连乘题目描述 解题代码void printOptimalParens(vector<vector<int>>& partition, int i, int j) { if (i == j) cout << "A" << i; // 单个矩阵，无需划分 else { cout << "("; printOptimalParens(partition, i, partition[i][j]); printOptimalParens(partition, partition[i][j] + 1, j); cout << ")"; } } // nums[i]: nums[0]为矩阵A1的行数，nums[i](i >= 1)表示矩阵Ai的列数 // 如输入为 nums = { 30,35,15,5,10,20,25 }，代表矩阵行列数如下： // A1: 30 * 35, A2: 35 * 15, A3: 15 * 5, A4: 5 * ...

棋盘覆盖题目描述 解题代码// para: 棋盘，行偏移，列偏移，特殊行，特殊列 void dividedCovering(vector<vector<int>>& chessBoard, int dr, int dc, int sr, int sc, int size) { if (size == 1) return; size /= 2; // 划分为四部分 if (sr < dr + size && sc < dc + size) { // 特殊点位于左上部分 divideCovering(chessBoard, dr, dc, sr, sc, size); } else { int nr = dr + size - 1, nc = dc + size - 1; // 新覆盖点 chessBoard[nr][nc] = 1; divideCovering(chessBoard, dr, dc, nr, nc, size); } if (sr < ...