如何运用树状数组实现区间操作查找的前缀和与差分算法？

本文共计1636个文字，预计阅读时间需要7分钟。

今天学习了前缀和差分，为了防止我把它忘掉，我简单记录一下。首先，需要知道什么是前缀和与差分：前缀和就是数组中某个元素之前所有元素的和，设b[]为前缀和数组，则b[i]就是数组a[]中前i个元素的和。

今天学了前缀和和差分，为了避免我把它忘掉，我还是浅浅的记录一下吧

首先需要知道什么是前缀和与差分：

前缀和就是数组中某元素之前（包括此元素）的所有元素的和

设b[]为前缀和数组，a[]是原数组。

对于一维数组而言，某个元素的前缀和就是从这个数组的第0个元素到这个元素的所有元素之和。

即：

那么就可以对区间求和产生更深刻的理解：

对于求出一个区间[l,r]的所有元素之和，我们就可以将首元素的前缀和与末元素的前缀合相减。