二叉索引树¶

/**
 * 树状数组
 * Binary Indexed Tree / Fenwick Tree
 * 
 * 1. 树状数组第一个元素为空节点
 * 2. y = x + (x & -x) <=等价于=> y 是 x 父节点
 * */
export default class FenwickTree {
  constructor(arraySize) {
    this.arraySize = arraySize;

    // Fill tree array with zeros.
    this.treeArray = Array(this.arraySize + 1).fill(0);
  }

  /**
   * 若 treeArray[y] 是 treeArray[x] 的父节点，
   * 则需满足 y = x + (x & -x)
   * */
  static lowbit (x) {
    return x & -x;
  }

  /**
   * Adds value to existing value at position.
   * */
  increase(position, value) {
    if (position < 1 || position > this.arraySize) {
      return false;
    }

    for (let i = position; i <= this.arraySize; i += FenwickTree.lowbit(i)) {
      this.treeArray[i] += value;
    }

    return this;
  }

  /**
   * 前缀和查询
   * Query sum from index 1 to position.
   *
   * @param  {number} position
   * @return {number}
   */
  query(position) {
    if (position < 1 || position > this.arraySize) {
      return null;
    }

    let sum = 0;

    for (let i = position; i > 0; i -= FenwickTree.lowbit(i)) {
      sum += this.treeArray[i];
    }

    return sum;
  }

  /**
   * Query sum from index leftIndex to rightIndex.
   */
  queryRange(leftIndex, rightIndex) {
    if (leftIndex > rightIndex) {
      return null;
    }

    if (leftIndex === 1) {
      return this.query(rightIndex);
    }

    return this.query(rightIndex) - this.query(leftIndex - 1);
  }
}