二叉索引树

算法解析

对于二叉索引树的构造，我们使用类的方法：

fenwicktree.js

class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }
  // ...
}

之后，针对树状数组的快速更新、查找前缀和、求和编写如下三个成员函数：

fenwicktree.js

class FenwickTree {
  // ...
  update(i, delta) {
    while (i <= this.size) {
      this.tree[i] += delta;
      i += i & -i;
    }
  }

  query(i) {
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= i & -i;
    }
    return sum;
  }

  findKth(k) {
    let pos = 0;
    let bitMask = 1 << 20;
    while (bitMask > 0) {
      let nextPos = pos + bitMask;
      if (nextPos <= this.size && this.tree[nextPos] < k) {
        k -= this.tree[nextPos];
        pos = nextPos;
      }
      bitMask >>= 1;
    }
    return pos + 1;
  }
}

⛽️ 信息

对于更新和查找前缀和，我们都是对构造出来的树状数组下标为 i 的数字做修改，同时再对包含 i 的数字做查找。因为 tree 数组实际上保管的是以 i 为终点、长度为 lowbit 的信息（不局限于区间和，看下面的题目，也可以存放出现的频率）。

主要是理解 findKth 这个函数到底在做什么？

其实就是参考了二分查找的思想，但是采用的是位运算。先用一个大步查找位置，并且对于累计频次不到 K 的直接减去即可。过程中，对于步长再不断缩减，最终找到正确的位置。

题目回顾

回到 24 科大讯飞的秋招这道题，我们经过 Map 离散化得到的结果是这样的：Key 是数组里的数字，Value 是第几大。
我们接着初始化一个树状数组，会发现里面保存的数据相当于是一个频率表，对于排名第 X 的数据，频率都加一。
注意我们遍历的是原始数据，所以现在存的频率所有的数值和应该是原始数据数组长度。
循环就不解释了，取出每次序列里的中位数产生结果。重点是，如何理解循环里是在做什么？
k 就是第几小的元素，因为我们维护的 tree[] 是从 1 开始的，这里不要搞错。
接下来其实就是先通过 tree[] 找到你想要的位置（中位数下标）对应的离散编号。
有了离散编号之后，再反查真实数据。注意在排序数组里查找，要做 -1 工作，因为排序数组和编号数组分别是零基和一基。
最后做频率更新和数组长度更新。

二叉索引树 ​

算法解析 ​

题目回顾 ​

二叉索引树

算法解析

题目回顾