树状数组可以做哪些问题

树状数组可以解决以下问题：

1. 区间求和问题：给定一个数组，支持单点修改和区间求和。

2. 区间最大值、最小值问题：给定一个数组，支持单点修改和区间查询最大值或最小值。

3. 求逆序对问题：给定一个数组，求其中逆序对的数量。

4. 求前缀和问题：给定一个长度为n的数组a和一个长度为m的询问序列，每次询问给出一个下标i，要求计算a[0]到a[i]的和。

5. 求区间众数问题：给定一个数组，支持区间查询众数。

6. 求区间第k大（小）数问题：给定一个数组，支持区间查询第k大（小）数。

7. 求区间不同数的个数问题：给定一个数组，支持区间查询不同数的个数。

8. 求区间和的最大值问题：给定一个数组，支持区间查询和的最大值。

9. 求区间和的最小值问题：给定一个数组，支持区间查询和的最小值。

10. 求区间内的众数问题：给定一个数组，支持区间查询众数。

11. 求区间内的最大值和最小值的差值问题：给定一个数组，支持区间查询最大值和最小值的差值。

12. 求区间内的平均数问题：给定一个数组，支持区间查询平均数。

13. 求区间内的中位数问题：给定一个数组，支持区间查询中位数。

14. 求区间内的最长连续递增（递减）序列问题：给定一个数组，支持区间查询最长连续递增（递减）序列。

15. 求区间的两个数的最大公约数问题：给定一个数组，支持区间查询两个数的最大公约数。

相关问题

用树状数组解决窗口的星星问题

窗口的星星问题是一个经典的二维离散化问题，解决该问题可以使用树状数组（Binary Indexed Tree，BIT）。

首先，我们需要离散化二维平面，将所有点的坐标映射为一个从 1 到 n 的连续整数，方便使用树状数组进行计算。

接下来，我们需要定义树状数组的两个操作：单点修改和区间查询。单点修改用于将某个点的星星数量加上一个指定的值，区间查询用于查询某个矩形区域内的星星数量。

对于单点修改，我们可以通过不断将当前点的最低位加上 1，直到达到树状数组的最大值，同时更新下一个需要修改的点的下标。

对于区间查询，我们可以通过计算矩形区域的四个顶点在树状数组上的前缀和，然后对相邻的两个前缀和进行加减操作得到矩形区域内的星星数量。

综上所述，使用树状数组可以解决窗口的星星问题，时间复杂度为 O(nlogn)。

线性数组转化为树形数组

线性数组可以通过一定的规律转化为树形数组，具体的方法如下：

1. 定义树形数组

首先，我们需要明确树形数组的定义。树形数组是一种特殊的数组，它可以用来表示一棵二叉树。在树形数组中，每个节点的左子节点存储在下标为 2i 的位置上，右子节点存储在下标为 2i+1 的位置上（i 为节点的下标）。根节点存储在下标为 1 的位置上。

2. 确定线性数组的规律

接下来，我们需要确定线性数组的规律。线性数组一般是按照某种顺序排列的，比如按照层序遍历的顺序排列。我们需要找出每个节点在线性数组中的位置和它在树形数组中的位置之间的关系。

3. 转化为树形数组

有了上述两个步骤的准备，我们就可以开始将线性数组转化为树形数组了。具体步骤如下：

- 定义一个空的树形数组。
- 遍历线性数组中的每个节点，按照其在树形数组中应该存储的位置，将其存储到树形数组中。
- 遍历完成后，树形数组就构建完成了。

举个例子，假设我们有如下的线性数组：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

按照层序遍历的顺序，第一个节点是根节点，其余节点的左右子节点依次排列。因此，我们可以得到如下的树形数组：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

根节点存储在下标为 1 的位置上，左子节点存储在下标为 2 的位置上，右子节点存储在下标为 3 的位置上，以此类推。在树形数组中，下标为 0 的位置是空的，不存储任何节点。