数据结构与算法专题——第六题 树状数组
16lz
2021-02-24
有一种数据结构是神奇的，神秘的，它展现了位运算与数组结合的神奇魅力，它就是树状数组，这种数据结构不是神人是发现不了的。
一: 概序
假如我现在有个需求，就是要频繁的求数组的前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];
·· 无奈数学公式不支持，只能截一张图啦 ··
二: 代码
1. 神奇的Lowbit函数
/// <summary>
/// 当前的sum数列的起始下标
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public static int Lowbit(int i)
{
return i & -i;
}
2:求前n项和
比如上图中，如何求Sum(6)，很显然Sum(6)=S4+S6，那么如何寻找S4呢？即找到6以前的所有最大子树，很显然这个求和的复杂度为logN。
/// <summary>
/// 求前n项和
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
public static int Sum(int x)
{
int ans = 0;
var i = x;
while (i > 0)
{
ans += sumArray[i - 1];
//当前项的最大子树
i -= Lowbit(i);
}
return ans;
}
3：修改
如上图中，如果我修改了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;
}
}
最后上总的代码:
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();
}
/// <summary>
/// 初始化两个数组
/// </summary>
public static void Init()
{
for (int i = 1; i <= 8; i++)
{
arr[i - 1] = i;
//设置其实坐标：i=1开始
int start = (i - Lowbit(i));
var sum = 0;
while (start < i)
{
sum += arr[start];
start++;
}
sumArray[i - 1] = sum;
}
}
public 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;
}
}
/// <summary>
/// 求前n项和
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
public static int Sum(int x)
{
int ans = 0;
var i = x;
while (i > 0)
{
ans += sumArray[i - 1];
//当前项的最大子树
i -= Lowbit(i);
}
return ans;
}
/// <summary>
/// 当前的sum数列的起始下标
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public static int Lowbit(int i)
{
return i & -i;
}
}
更多相关文章
- 数据结构与算法专题——第一题 Bitmap算法
- 结构体作业讲解（零基础学习C语言）
- Python数据分析常用库有哪些?Python学习！
- 0129-数组的排序, 数组的合并, 数组成员的统计
- 第5章 0129-细说常用的数组函数，学习心得、笔记（数组的排序, 数组
- php数据类型与检测
- 指针经典笔试题解析（C语言）
- 指针进阶（一）（详细讲解1,2,3）（零基础学习C语言）
- 2021-2-17：Java HashMap 的中 key 的哈希值是如何计算的，为何这么