结果，天亮后一睁眼，发现——隔壁床竟然多了一个人，接着一问，才知道原来躺在那儿的是HR大大！
算法题：区域和检索 - 数组可修改
今天我们来聊一聊一道算法题，题目名字挺长的：区域和检索 - 数组可修改。
这道题的背景很简单：给定一个数组，我们要支持两种操作：
更新数组中某个位置的值。 查询数组某个区间的和。
别小看这两个操作，尤其是查询和的操作，它是一个经典的“区间查询”问题，很多时候我们需要频繁地对数组进行求和，传统的做法可能会很低效，尤其是当数据量很大时。这个问题的关键就是：怎么能高效地支持快速查询的同时，又不影响更新操作的效率。
一开始，我会想到暴力解法。比如说，我们就每次查询区间和时直接遍历数组区间，这样时间复杂度就是O(n)，每次更新数组元素时也是O(1)。可是，你能忍受每次查询都O(n)吗？我猜大多数人都会很抓狂。尤其是当你查询操作频繁时，时间复杂度的瓶颈就凸显出来了。
那么，如何优化这个问题呢？我们不妨借用一些经典的数据结构，比如线段树或树状数组（Binary Indexed Tree, BIT）。它们都能在O(log n)时间内完成区间求和和单点更新操作，简直是“神器”！
我个人更倾向于树状数组，它实现起来相对简单，不像线段树那样需要复杂的合并和区间分治。树状数组的思路是利用数组元素的二进制位来巧妙地“压缩”计算，具体来说，它通过记录每个位置与某个区间的“累积和”，从而可以在O(log n)时间内快速查询到任意区间的和。
代码实现大概是这样的：
class NumArray {
private int[] bit; // 树状数组
private int n;
public NumArray(int[] nums) {
n = nums.length;
bit = new int[n + 1]; // bit数组从1开始
for (int i = 0; i < n; i++) {
update(i, nums[i]);
}
}
// 树状数组的更新操作
private void update(int index, int val) {
index++; // 树状数组从1开始
while (index <= n) {
bit[index] += val;
index += index & -index; // 找到下一个需要更新的位置
}
}
// 查询区间和
public int sumRange(int left, int right) {
return sum(right) - sum(left - 1);
}
// 查询前缀和
private int sum(int index) {
index++; // 树状数组从1开始
int result = 0;
while (index > 0) {
result += bit[index];
index -= index & -index; // 查找上一个累积的区间
}
return result;
}
}
这里我定义了一个NumArray类，构造方法接受一个整数数组nums，并通过调用update方法将每个元素插入到树状数组bit中。update方法的作用是更新树状数组中的值，使得后续的查询可以通过快速累积来完成。
接着，sumRange方法用来查询指定区间的和。通过前缀和技巧，我们可以利用sum(right) - sum(left - 1)来获取任意区间的和，而sum方法负责计算前缀和。
这种做法的优点就是：更新操作O(log n)，查询操作也是O(log n)，比暴力解法快得多，尤其是在大数据量的情况下，性能提升非常明显。
那如果题目要求在进行大量查询的同时频繁更新呢？那就可以更灵活地选择数据结构了。比如线段树虽然在实现上要复杂一些，但它的优势在于支持区间修改操作。如果需要进行区间修改而不是单点更新，线段树就更合适了。
不过，话说回来，虽然树状数组的实现相对简单，但是它也不是万能的。如果你在实际开发中遇到一些更复杂的需求，比如支持区间修改或其他特殊操作，那么线段树、平衡树等结构可能就更具优势了。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
