树状数组学习笔记
2025-10-25 13:57:59
发布于:上海
纯属娱乐的一个帖子,给自己复习用的。不是给人学习用的。
我的学习方法是直接抄。如果真想要学请看:
https://www.luogu.com.cn/article/em3jlsrx
树状数组:查询和修改复杂度都为O(logn)的数据结构。
其主要用途为数组单点修改与求区间和。
效率比线段树要高很多。
梳妆属于基于二进制唯一分解性质。
基本用途是围护序列前缀和。
对于一个区间[1,x],树状数组将其分为log(x)个小区间,从而快速求取区间和。
若数字x的二进制表示为(10101)。
我们将一个数的二进制分解后最小的那一个幂称为lowbit(x)。
lowbit(x)=x&(-x)
一个区间[l,r]的长度即为lowbit(r)。
所以区间又可以表示为[r-lowbit(r)+1,r]
所以,对于给定的数组A,我们可以建立数组T,
这里空空如也







有帮助,赞一个