type
status
date
slug
summary
tags
category
icon
password
简介
树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。
普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。
事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小。
有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的 区间加单点值 和 区间加区间和 问题。
树状数组能快速求解信息的原因：我们总能将一段前缀 拆成 不多于 段区间，使得这 段区间的信息是已知的。
于是，我们只需合并这 段区间的信息，就可以得到答案。相比于原来直接合并 个信息，效率有了很大的提高。
不难发现信息必须满足结合律，否则就不能像上面这样合并了。
管辖区间
树状数组中，规定 管辖的区间长度为 ，其中：
- 设二进制最低位为第 位，则 恰好为二进制表示中，最低位的 所在的二进制位数。
- （ 的管辖区间长度）恰好为 二进制表示中，最低位的 以及后面所有 组成的数。
举个例子， 管辖的是哪个区间?
因为 ，其二进制最低位的 以及后面的 组成的二进制是 ，即 ，所以 管辖 个 数组中的元素。因此， 代表 的区间信息。
我们记： 二进制最低位 以及后面的 组成的数为 ，那么 管辖的区间就是 。
这里注意：lowbit 指的不是最低位 所在的位数 ，而是这个 和后面所有 组成的 。
实现代码：
区间查询
数组是用来储存原始数组 某段区间的和的，也就是说，这些区间的信息是已知的，我们的目标就是把查询前缀拆成这些小区间。
举例：计算 的和。
我们还是从 开始跳，跳到 再跳到 。此时我们发现它管理了 的和，但是我们不想
要 这一部分，怎么办呢？很简单，减去 的和就行了。
那不妨考虑最开始，就将査询 的和转化为査询 的和，以及査询 的和，最终将两个结果作差。
其实任何一个区间査询都可以这么做：査询 的和，就是 的和减去 的和，从而把区间问题转化为前缀问题，更方便处理。
我们可以写出査询 的过程:
- 从 开始往前跳，有 管辖 。
- 令，如果 说明已经跳到尽头了，终止循环，否则回到第一步
- 将跳到的c合并。
单点修改
设 表示 的大小，不难写出单点修改 的过程：
- 初始令 。
- 修改 。
- 令 ，如果 说明已经跳到尽头了，终止循环，否则回到第二步。
区间信息和单点修改的种类，共同决定 的修改方式。下面给几个例子：
- 若 维护区间和，修改种类是将 加上 ，则修改方式则是将所有 也加上 。
- 若 维护区间积，修改种类是将 乘上 ，则修改方式则是将所有 也乘上 。
实现代码：
建树
也就是根据最开始给出的序列，将树状数组建出来（c全部预处理好）
一般可以直接转化为 次单点修改，时间复杂度 。
建树
以维护区间和为例。
方法一：
每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献，即每次确定完儿子的值后，用自己的值更新自己的直接父亲。
方法二：
前面讲到 表示的区间是 ，那么我们可以先预处理一个 前缀和数组，再计算 数组。
模板例题
单点修改与区间查询
区间修改与单点查询
我们用树状数组保存差分即可实现区间修改。
另一个写法是树状数组存相邻个两数之间的差值，在此不做演示。
二维树状数组
二维树状数组差分
由二维差分的知识可知，我们需要维护四个数组。
树状数组求逆序对
- Author:Serendipity
- URL:https://serendipity565.netlify.app//article/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!