树状数组求逆序对 树状数组的几种用法?
树状数组的几种用法?
假设数组的长度为n,线段树和树数组的基本功能是在满足约束律的一定运算(如加法、乘法、最大值、最小值)下,修改单个元素,并在o(logn)时间复杂度内保持区间信息。不同的是树数组只能维护前缀“运算和”(前缀和、前缀积、前缀max min),而段树可以维护区间运算和。但有些运算有逆元素,这给人一种错觉,认为树数组可以保持区间信息:保持区间和、模素数意义上的区间积、区间异或和。这样做的实质是取右端点的前缀和,然后对左端点的前缀和的逆做一个操作,所以树数组的区间查询实际上是两个前缀和查询。可见树数组可以保留某些运算的区间信息,但不能保留其它运算的区间信息:Max/min值,模非素数意义下的乘法,因为这些运算中没有逆元素,所以不能使用两个前缀的和。但是片段树是不同的。分段树直接维护区间信息,所有满足组合规则的操作都可以维护区间和,而懒标记的存在也使得分段树支持区间修改,这是树数组所不能做到的。可以说树数组所能做的实际上是线段树的子集。在大多数情况下,真正使用树数组仅仅是因为它易于编写,而且它的常量很小。然而,随着zkw段树的流行,树数组仅有的两个优点已经不复存在了,我想这将是一个巨大的挑战。兴趣相关:弱省、弱校、弱菜。我们只能讨论一些基本功能。请不要在这个答案中谈论树数组的高级用法,因为我真的还没有学会
算法,其实就是解决问题的方法。学习算法是学习前人解决问题的方法。为什么要学习算法?想要在编程道路上走得更远的程序员可能需要学习算法。我记得在软件工程中,程序是数据结构算法,这说明了算法对程序的重要性。
许多初级业务系统程序员可能不会使用很多数学公式,但这并不意味着他们不使用算法。算法代表了数学对于计算机的重要性,对于图形和图像、人工智能等方面来说,数学基础不好,不懂的算法可以说是很难的。
即使你不是程序员,你也应该学习更多关于算法的知识。一方面有助于思维训练,另一方面也有助于解决生活中的实际问题。例如:用矩阵解方程。
每个人学习算法的目的可能不同,但算法对学习者的实际好处是相同的。
树状数组求逆序对 树状数组简单易懂的详解 面试问为什么加入字节跳动
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。