伍佰目录 短网址
  当前位置:海洋目录网 » 站长资讯 » 教育考试 » 文章详细 订阅RssFeed

数据结构与算法专题——第六题 树状数组

来源:本站原创 浏览:84次 时间:2022-12-12

有一种数据结构是神奇的,神秘的,它展现了位运算与数组结合的神奇魅力,它就是树状数组,这种数据结构不是神人是发现不了的。

一: 概序

假如我现在有个需求,就是要频繁的求数组的前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;
       }
   }


  推荐站点

  • At-lib分类目录At-lib分类目录

    At-lib网站分类目录汇集全国所有高质量网站,是中国权威的中文网站分类目录,给站长提供免费网址目录提交收录和推荐最新最全的优秀网站大全是名站导航之家

    www.at-lib.cn
  • 中国链接目录中国链接目录

    中国链接目录简称链接目录,是收录优秀网站和淘宝网店的网站分类目录,为您提供优质的网址导航服务,也是网店进行收录推广,站长免费推广网站、加快百度收录、增加友情链接和网站外链的平台。

    www.cnlink.org
  • 35目录网35目录网

    35目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向35目录推荐、提交优秀网站。

    www.35mulu.com
  • 就要爱网站目录就要爱网站目录

    就要爱网站目录,按主题和类别列出网站。所有提交的网站都经过人工审查,确保质量和无垃圾邮件的结果。

    www.912219.com
  • 伍佰目录伍佰目录

    伍佰网站目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向伍佰目录推荐、提交优秀网站。

    www.wbwb.net