首页 > 其他分享 >树状数组

树状数组

时间:2023-08-09 16:57:12浏览次数:51  
标签:log 树状 sum 数组 ans 复杂度

初步感受

已知 \(a_i\),求 \(\sum_{i=1}^7 a_i\)。

暴力

\(ans=a_1+a_2+a_3+a_4+a_5+a_6+a_7\)

时间复杂度:\(O(n)\)

树状数组

已知 \(A=\sum_{i=1}^4 a_i\),\(B=\sum_{i=5}^6 a_i\),\(C=\sum_{i=7}^7 a_i\),则 \(ans=A+B+C\)

时间复杂度:\(O(\log n)\)

这就是树状数组能快速求解信息的原因:我们总能将一段前缀 \([1,n]\) 拆成 不多于 \(\log n\) 段区间,使得这 \(\log n\) 段区间的信息是 已知的。

于是,我们只需合并这 \(\log n\) 段区间的信息,就可以得到答案。相比于原来直接合并 \(n\) 个信息,效率有了很大的提高。

树状数组具体长这样:

image

标签:log,树状,sum,数组,ans,复杂度
From: https://www.cnblogs.com/reclusive2007/p/17617246.html

相关文章

  • luogu P4200 千山鸟飞绝 题解 【一维数组套平衡树】
    目录题目解题思路code题目题目链接解题思路首先,此题有明显的插入、删除、查找,所以必须要使用平衡树。考虑如何使用平衡树维护每个鸟的状态。发现很不方便,因为鸟的位置改变,整个平衡树的值都要修改。考虑针对每个节点开一颗平衡树,这样就有\(3e4\times3e4\)棵树。这显然太多了......
  • TypeScript中使用数组的filter方法
    constarr:string[]=['pom','皮蛋编程','非常厉害','太棒了'];constfilteredArr:string[]=arr.filter((str:string)=>{returnstr.includes('编程');});console.log(filteredArr);//["皮蛋编程"] ar......
  • 2023-08-08:给你一棵 n 个节点的树(连通无向无环的图) 节点编号从 0 到 n - 1 且恰好有 n
    2023-08-08:给你一棵n个节点的树(连通无向无环的图)节点编号从0到n-1且恰好有n-1条边给你一个长度为n下标从0开始的整数数组vals分别表示每个节点的值同时给你一个二维整数数组edges其中edges[i]=[ai,bi]表示节点ai和bi之间有一条无向边一条好路......
  • 2023-08-08:给你一棵 n 个节点的树(连通无向无环的图) 节点编号从 0 到 n - 1 且恰好有 n
    2023-08-08:给你一棵n个节点的树(连通无向无环的图)节点编号从0到n-1且恰好有n-1条边给你一个长度为n下标从0开始的整数数组vals分别表示每个节点的值同时给你一个二维整数数组edges其中edges[i]=[ai,bi]表示节点ai和bi之间有一条无向边一条好路径需要......
  • 树状数组学习笔记
    树状数组作为一个常数小且好写的数据结构,虽然功能没有线段树那么齐全,但是其中的扩展内容还是很多的。维护区间和1.0BIT的作用树状数组可以做到单次logn求前缀和,单次logn修改信息维护一个前缀和。1.1区间修改单点查询考虑维护差分数组\(c[i]=a[i]-a[i-1]\)。在查询......
  • 前端基础-数组方法
    数组方法备忘单:添加/删除元素:push(...items) ——向尾端添加元素,pop() ——从尾端提取一个元素,shift() ——从首端提取一个元素,unshift(...items) ——向首端添加元素,splice(pos,deleteCount,...items) ——从 pos 开始删除 deleteCount 个元素,并插入 i......
  • 树状数组
    大佬的讲解视频讲解两者搭配食用效果更佳树状数组就是一个树状数组的板子题intlowbit(intx){returnx&(-x);}求最低位1代表的值是多少voidadd(intx,inty){while(x<=n){c[x]+=y;x+=lowbit(x);}}将包含这个数的每一个值都更新int......
  • 笔记 | 类数组与数组扁平化
    一、类数组Array-like在日常中能接触到的类数组有这么几个:参数对象arguments;通过querySelector获取的NodeList;NodeList对象是节点集合,NodeList可以使用for...of来迭代,在一些情况下,NodeList是一个实时合集;通过函数:getElementsByTagNamegetElementsByClass......
  • JS实现根据数组对象的某一属性排序
    一、冒泡排序(先了解冒泡排序机制)以从小到大排序为例,冒泡排序的原理就是通过两层循环把数组中两两相邻的元素进行比较,是的大的元素放到后边,元素交换位置,从而一步步的交换元素的位置,使得最大的元素放到数组的末尾,这样内部的循环就进行了一轮,再根据外部的循环依次再把次大一点的元素......
  • 对集合数组进行降序排列的方法
    在Dart中,你可以使用List的sort()方法对集合数组进行排序。要按降序排列,可以在排序方法中指定一个自定义的比较函数。以下是一种常见的降序排序方法:List<int>numbers=[3,1,4,2,5];numbers.sort((a,b)=>b.compareTo(a));print(numbers);//[5,4,3,2,1]在上述示例中,......