树状数组简单易懂的详解,树状数组 线段树

　　关键词：前缀和的位运算、查询和更新。

　　第一节用树型数组解决问题树型数组也叫“二叉索引树”或芬威克树。

　　它可以高效地实现以下两种操作：

　　数组的前缀和查询；数组的“单点更新”。

　　下面详细解释这两种操作。

　　首先，看看下面的例子，看看数组的前缀和查询是什么。

　　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树是一种可以快速计算前缀和以及单点更新的数据结构。

　　(本节结束)

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。