差分数组为何能用两次操作完成区间修改从前缀和逆运算到LeetCode完整通关指南
假设有一个长度为10000的数组，需要对区间[100, 5000]内的每个元素都加3，然后再对区间[200, 8000]内的每个元素减5，最后还要对区间[1000, 9000]内的每个元素加10。这样的操作要重复进行1000次，最后输出最终结果。 ...
前缀和
树状数组：用最少的代码实现最高效的区间查询从lowbit到LeetCode完整通关指南
1994年，新西兰奥克兰大学的 Peter M. Fenwick 在《Software: Practice and Experience》期刊上发表了一篇题为"A new data structure for cumulative frequency tables"的论文。这篇看似平淡无奇的论文，却发明了一个代码量极小却威力巨大的数据结构——树状数组（Binary Indexed Tree，简称 BIT），也被称为 Fenwick Tree。 ...
前缀和算法如何用一次预处理换来O(1)区间查询
给定一个长度为100万的数组，需要回答10万次查询——每次查询要求计算某个区间的元素之和。最直观的做法是：对每个查询，遍历从左端点到右端点的所有元素进行累加。假设平均区间长度为50万，总操作次数约为500亿次，在现代CPU上需要运行数秒甚至更久。 ...