诸城做网站的公司,设计网站公司地址,网站支付接口如何做,html网页制作免费模板下载有一种数据结构是神奇的#xff0c;神秘的#xff0c;它展现了位运算与数组结合的神奇魅力#xff0c;太牛逼的#xff0c;它就是树状数组#xff0c;这种数据结构不是神人是发现不了的。
一、概序
假如我现在有个需求#xff0c;就是要频繁的求数组的前 n 项和#x…有一种数据结构是神奇的神秘的它展现了位运算与数组结合的神奇魅力太牛逼的它就是树状数组这种数据结构不是神人是发现不了的。
一、概序
假如我现在有个需求就是要频繁的求数组的前 n 项和并且存在着数组中某些数字的频繁修改那么我们该如何实现这样的需求当然大家可以往真实项目上靠一靠。 **① 传统方法**根据索引修改为 O(1)但是求前 n 项和为 O(n)。 **② 空间换时间方法**我开一个数组 sum[]sum[i]a[1]…a[i]那么有点意思求 n 项和为 O(1)但是修改却成了 O(N)这是因为我的 Sum[i]中牵涉的数据太多了那么问题来了我能不能在相应的 sum[i]中只保存某些 a[i]的值呢好吧下面我们看张图。 从图中我们可以看到 S[]的分布变成了一颗树有意思吧下面我们看看 S[i]中到底存放着哪些 a[i]的值。
S[1]a[1];
S[2]a[1]a[2];
S[3]a[3];
S[4]a[1]a[2]a[3]a[4];
S[5]a[5];
S[6]a[5]a[6];
S[7]a[7];
S[8]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8];之所以采用这样的分布方式是因为我们使用的是这样的一个公式S[i]a[i-2k1]…a[i]。 其中2k 中的 k 表示当前 S[i]在树中的层数它的值就是 i 的二进制中末尾连续 0 的个数2k 也就是表示 S[i]中包含了哪些 a[]举个例子: i61001102 可以发现末尾连续的 0 有一个即 k1则说明 S[6]是在树中的第二层并且 S[6]中有 21 项随后我们求出了起始项 a[6-211]a[5]但是在编码中求出 k 的值还是有点麻烦的所以我们采用更灵巧的 Lowbit 技术即2ki-i 。 则S[6]a[6-211]a[6-(6-6)1]a[5]a[6]。
二、代码
1、神奇的 Lowbit 函数 #region 当前的sum数列的起始下标/// summary/// 当前的sum数列的起始下标/// /summary/// param namei/param/// returns/returnspublic static int Lowbit(int i){return i -i;}#endregion2、求前 n 项和
比如上图中如何求 Sum(6)很显然 Sum(6)S4S6那么如何寻找 S4 呢即找到 6 以前的所有最大子树很显然这个求和的复杂度为 logN。 #region 求前n项和/// summary/// 求前n项和/// /summary/// param namex/param/// returns/returnspublic static int Sum(int x){int ans 0;var i x;while (i 0){ans sumArray[i - 1];//当前项的最大子树i - Lowbit(i);}return ans;}#endregion3、修改
如上图中如果我修改了 a[5]的值那么包含 a[5]的 S[5]S[6]S[8]的区间值都需要同步修改,我们看到只要沿着 S[5]一直回溯到根即可同样它的时间复杂度也为 logN。 public static void Modify(int x, int newValue){//拿出原数组的值var oldValue arr[x];for (int i x; i arr.Length; i Lowbit(i 1)){//减去老值换一个新值sumArray[i] sumArray[i] - oldValue newValue;}}最后上总的代码: using System;using System.Collections.Generic;using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;namespace ConsoleApplication2
{public class Program{static int[] sumArray new int[8];static int[] arr new int[8];public static void Main(){Init();Console.WriteLine(A数组的值:{0}, string.Join(,, arr));Console.WriteLine(S数组的值:{0}, string.Join(,, sumArray));Console.WriteLine(修改A[1]的值为3);Modify(1, 3);Console.WriteLine(A数组的值:{0}, string.Join(,, arr));Console.WriteLine(S数组的值:{0}, string.Join(,, sumArray));Console.Read();}#region 初始化两个数组/// summary/// 初始化两个数组/// /summarypublic static void Init(){for (int i 1; i 8; i){arr[i - 1] i;//设置其实坐标i1开始int start (i - Lowbit(i));var sum 0;while (start i){sum arr[start];start;}sumArray[i - 1] sum;}}#endregionpublic static void Modify(int x, int newValue){//拿出原数组的值var oldValue arr[x];arr[x] newValue;for (int i x; i arr.Length; i Lowbit(i 1)){//减去老值换一个新值sumArray[i] sumArray[i] - oldValue newValue;}}#region 求前n项和/// summary/// 求前n项和/// /summary/// param namex/param/// returns/returnspublic static int Sum(int x){int ans 0;var i x;while (i 0){ans sumArray[i - 1];//当前项的最大子树i - Lowbit(i);}return ans;}#endregion#region 当前的sum数列的起始下标/// summary/// 当前的sum数列的起始下标/// /summary/// param namei/param/// returns/returnspublic static int Lowbit(int i){return i -i;}#endregion}
}
