数据结构-树状数组讲解

2024-08-28 07:18

本文主要是介绍数据结构-树状数组讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

树状数组的作用:树状数组是对一个数组 改变某个元素和 求和比较实用的数据结构。其中”求和,更改“两部操做的时间复杂度都是O(log(n)),n为数组元素个数。
在解题过程中,我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]。
但是不难发现,如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。
可以说,每次修改A[i]后,调整前缀和S[]在最坏情况下会需要O(n)的时间。
当n非常大时,程序会运行得非常缓慢  因此,这里我们引入“树状数组”,它的修改与求和都是O(logn)的,效率非常
================================================================================================
为了便于理解,我们看下图
其中A[]代表的是原有数组,而C[]就是树状数组。C[]存的是A[i-lowbit(i)+1]~A[i]的和。这里lowbit(i)代表的是i的二进制表示中从右往左第一个1对应的值例:lowbit(6)的值为2.{此处也可以真么理解: C[i]表示A[i-2^k+1]到A[i]的和,而k则是i在二进制时末尾0的个数,   同时,我们也不难发现,这个k就是该节点在树中的高度,因而这个树的高度不会超过logn。 }所以,我们在修改A[i]的时候可以从C[i]依次向上更改调整这条路上的所有C[]值, 这个操作的复杂度在最坏情况下就是树的高度即O(logn)。  另外,对于求数列的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。


         











     另外,对于求数列的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。

          不难发现,这些子树的数目是n在二进制时1的个数,或者说是把n展开成2的幂方和时的项数,

          因此,求和操作的复杂度也是O(logn)。

          接着,我们考察这两种操作下标变化的规律:

          首先看修改操作:

          已知下标i,求其父节点的下标。
          我们可以考虑对树从逻辑上转化:


         如图,我们将子树向右对称翻折,虚拟出一些空白结点(图中白色),将原树转化成完全二叉树。

         有图可知,对于节点i,其父节点的下标与翻折出的空白节点下标相同。

         因而父节点下标 p=i+2^k  (2^k是i用2的幂方和展开式中的最小幂,即i为根节点子树的规模)

         即  p = i + i&(i^(i-1)) 。

         接着对于求和操作:

         因为每棵子树覆盖的范围都是2的幂,所以我们要求子树i的前一棵树,只需让i减去2的最小幂即可。

         即  p = i - i&(i^(i-1)) 。

        

         至此,我们已经比较详细的分析了树状数组的复杂度和原理。

         在最后,我们将给出一些树状数组的实现代码,希望读者能够仔细体会其中的细节。

【代码】

  求lowbit(i)


int Lowbit(int t) 

    return t & ( -t ); 

             
  求前n项和:


int Sum(int i) 

    int sum = 0; 
    while(i > 0) 
    { 
        sum += c[i]; 
        i -= Lowbit(i); 
    } 
    return sum; 


 对某个元素进行加法操作: 

void add(int i , int d) 

    while(i<= n) 
    { 
          c[i] += d; 
           i+= Lowbit(i); 
    } 
参考: http://www.cppblog.com/Ylemzy/articles/98322.html

这篇关于数据结构-树状数组讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1114097

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };