专栏首页青青天空树小白初理解树状数组

小白初理解树状数组

  ACM的在线测试里经常涉及到大量数据的的修改,求和等操作,这里介绍一种方法——树状数组。

  树状数组,是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值。可以用一张图来弄懂什么是数组数组。

 原数组A[n],树状数组C[n];

如果n为奇数:Cn=An;

如果n为偶数:Cn = A(n – 2^k + 1) + ... + An,k为n的二进制数末尾0的个数。

可以用lowbit函数快速得到2^k,这里用到了位运算,&是位运算符,不细说。

int lowbit(int t)  { return t&(-t); }

该函数返回该树状数组节点的管辖范围,如C[6],带入6返回值为2,C[6]=A[5]+A[6];

更新树状数组函数upDate

void upDate(int x,int num) //修改树状数组 {   while(x<=N)   {     b[x]+=num;     x+=lowbit(x);   } }

x是要更新的节点,N为树状数组长度,num为修改的值,本函数将树状数组C[]中所有包含A[x]的节点更新。本函数可用于数组的修改,也可用于数组的建立。

求和函数getSum

int getSum(int x) //求0-x的和 {   int s=0;   while(x>0)   {     s+=b[x];     x-=lowbit(x);   }   return s; }

 如果要求数组m-n段的和可用getSum(n)-getSum(m);

有了以上三个函数最基本的树状数组就成型了。。

再深入。。。。。

我也无能为力了。。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《动物魔法学校》儿童学编程Scratch之“外观”部分

    导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

    一石匠人
  • 声音功能让儿童编程更有创造性

    导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

    一石匠人
  • SQL中GROUP BY用法示例

    GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

    Awesome_Tang
  • 我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

    事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

    一石匠人
  • 天干地支五行八卦的对应关系

    一石匠人
  • 什么样的人生才是有意义的人生——没有标准的标准答案

    【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空,浩瀚的宇宙中整个地球只是一粒浮尘,何况地球上一个小小的人类?在漫长的历...

    一石匠人
  • 【系统设置】CentOS 修改机器名

    ken.io
  • 复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

    从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

    haifeiWu
  • 一张图理清《梅花易数》梗概

    学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

    一石匠人
  • 儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

    儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

    一石匠人

扫码关注云+社区

领取腾讯云代金券