目录

• 树状数组(二叉索引树)
• • 一、前缀和数组
  • • 1. 数列与其前缀和数列
    • 2. 前缀和数组
    • • 2.1 前缀和数组的计算
    • 3. 前缀和数组的用途
    • 4. 前缀和数组的复杂度分析
    • • 4.1 空间复杂度O(n)
      • 4.1 时间复杂度
      • • 4.1.1 创建
        • 4.1.2 查询
        • 4.1.3 更新
    • 5. 前缀和数组适用性
• 二、树状数组
• • 1. 产生原因
  • 2. 作用
  • 3. 优化思路
  • • 3.1 前缀和与原数组的包含关系
    • 3.2 分区间求和
    • • 3.2.1 $C[i]$的求和区间
      • 3.2.2
  • 复杂度
  • • 树状数组元素与原数组元素的包含关系
  • 性质
  • 支持的操作
  • 初始化
  • • 1. 利用单点操作初始化
    • 2. 利用前缀和数组进行初始化
    • 3. 利用子结点之和初始化
  • BinaryIndexedTree类