树状数组简单易懂的详解,树状数组 线段树
关键词：前缀和的位运算、查询和更新。
第一节用树型数组解决问题树型数组也叫“二叉索引树”或芬威克树。
它可以高效地实现以下两种操作：
数组的前缀和查询；数组的“单点更新”。
下面详细解释这两种操作。
首先，看看下面的例子，看看数组的前缀和查询是什么。
1给定数组arr=[10，15，17，19，20，14，12]，求下标0到下标4的所有元素之和。
分析：
“前缀和”定义一个数组
从「头」开始的区间
，计算下标位置是 0
区间内所有元素的和；注意：要理解“前缀”的含义，下标位置必须从0开始计算；其他不是从0开始的数组的区间和可以转化为前面的问题。解决方案：在Python中，可以使用sum(arr[0:5])得到下标0到下标4的所有元素的和。说明：在Python的语法中，切片操作不包括设置目标值，所以arr [0: 5]=[arr [0]，arr [1]，arr [2]，arr [3]，arr [4]]。
数组的“单点更新”例2已知数组[10，15，17，19，20，14，12]。
将下标为4的元素增加2；将下标为6的元素减少3。分析：
给出这个例子只是为了让大家熟悉这个公式。“一点更新”不在乎这个数字“变成”什么。它的公式是
给出一个数变化了多少
，因为加一个数等于减这个数的倒数。所以以上两种配方其实可以合并成：将某个下标的元素增加多少；
。如果不使用任何数据结构，仅依靠定义，“单点更新”操作的时间复杂度为O (1) O(1) O(1)，数组“前缀和”查询的时间复杂度为O (n) O(n) O(n)。你要扫描这个区间的大量元素，才能得到这个区间的和。优化方法是：先计算一个“前缀和”数组，这个数组的每个元素的值对应原数组的前缀和。3给定数组arr=[1，2，3，4，5，6，7]，计算前缀和数组cumsum(arr)。解析：根据“前缀和”的定义，很容易计算出前缀和数组是cumsum (arr)=[1，3，6，10，15，21，28]。
Python代码：
arr=[1，2，3，4，5，6，7]cumsum=[0]* Len(arr)cumsum[0]=arr[0]for I in range(1，Len(arr)):cumsum[I]=cumsum[I-1]arr[I]print(cumsum)有了前缀sum数组，前缀sum的每次查询的时间复杂度就变成了O(1)O(1)O(1)O(1)，这样就很容易计算区间和。
4给定数组arr=[1，2，3，4，5，6，7]，求第3个元素到第7个元素的和(包括第7个元素)。
分析：
第3个元素到第7个元素(包括第7个元素)的和可以表示为sum(arr[2:7])；注意：哪个元素与下标的序数有位置偏移，Python中的切片不包含终点)；假设我们有前缀和数组，我们可以用O(1)O(1)O(1)O(1)O(1)时间复杂度完成这个问题。
第1个元素到第7个元素(包括第7个元素)的和可以表示为：Cumsum(arr[0:7])=nums[0]nums[1]nums[2]nums[3]nums[4]nums[5]nums[6]第1个元素到第2个元素(包括
cumsum(arr[0:2])=nums[0]nums[1]所以第3个元素到第7个元素的和(包括第7个元素):
sum(arr[2:7])=cumsum(arr[0:7])-cumsum(arr[0:2])那么问题来了：要执行“单点更新”操作，必须更新前缀和数组，并且必须重新计算前缀和，时间复杂度为o (n) o (n) o(如果在那个业务场景中有多次计算前缀和以及单点更新操作，那么使用前缀和数组的效率会很低。Fenwick树是一种可以快速计算前缀和以及单点更新的数据结构。
(本节结束)
