0315.md

• 倒序遍历数组，按升序保存到一个序列中，每次插入到序列中，插入位置的索引即为原数组右侧小的元素数。虽然二分查找复杂度为 O(log n)，但插入为 O(n)，总体时间复杂度 O(n ^ 2)

class Solution {
 public:
  vector<int> countSmaller(vector<int>& nums) {
    int sz = size(nums);
    vector<int> res(sz);
    vector<int> v;
    for (int i = sz - 1; i >= 0; --i) {
      auto it = lower_bound(begin(v), end(v), nums[i]);
      res[i] = it - begin(v);
      v.emplace(it, nums[i]);
    }
    return res;
  }
};

• 使用二叉搜索树，插入操作时间复杂度 O(log n)，总体时间复杂度 O(n log n)

class Solution {
 public:
  struct Node {
    int val;
    int cnt = 0;
    int equal = 1;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int v) : val(v) {}
  };

  vector<int> countSmaller(vector<int>& nums) {
    if (empty(nums)) {
      return {};
    }
    Node* root = new Node(nums.back());
    vector<int> res(size(nums));
    for (int i = size(nums) - 2; i >= 0; --i) {
      res[i] = insert(root, nums[i]);
    }
    return res;
  }

 private:
  int insert(Node* node, int val) {
    if (val < node->val) {
      ++node->cnt;
      if (!node->left) {
        node->left = new Node(val);
        return 0;
      }
      return insert(node->left, val);
    }
    if (val > node->val) {
      if (!node->right) {
        node->right = new Node(val);
        return node->cnt + node->equal;
      }
      return node->cnt + node->equal + insert(node->right, val);
    }
    ++node->equal;
    return node->cnt;
  }
};

• 树状数组可以方便地计算数组一段区间的所有元素和，该问题可以转化为计算前缀和。正如所有整数可以表示为 2 的幂和，一个序列也可以表示为一系列子序列的和。为此首先需要引入一个辅助函数 lowbit，它返回二进制数最后一个 1 的位置所表示的值

int lowbit(int n) { return n & (~n + 1); }

int main() {
  assert(lowbit(0b10001101) == 1);
  assert(lowbit(0b11011010) == 2);
  assert(lowbit(0b10101100) == 4);
  assert(lowbit(0b10111000) == 8);
  assert(lowbit(0b11010000) == 16);
}

• lowbit 的原理如下

xxxx xxxx xxxx 1000

按位取反 => yyyy yyyy yyyy 0111
取反加 1 => yyyy yyyy yyyy 1000

与原有数进行与运算，即可消除最后的 1 之前的数

  xxxx xxxx xxxx 1000
& yyyy yyyy yyyy 1000
= 0000 0000 0000 1000

• 在计算机中，用二进制来表示一个数，数的表示方式有原码、反码、补码三种。对于有符号数，原码的最高位为符号位，其它位为数值位，符号位为 0 表示正数，符号位为 1 表示负数。原码对人来说很直观，但对计算机来说并不方便

对于数值 0，如果用原码表示，则有 `+0` 和 `-0` 两种情况
对于减法操作，如 1 - 1，不能转换为加法 1 + (-1)
原码：0 0001 + 1 0001 = 1 0010 = -2

• 计算机中实际使用的是补码，正数的补码与原码相同（正数的反码也与原码相同），负数的补码是反码（负数的反码即对原码的数值位按位取反）加 1，使用补码，即可统一处理加法和减法，即 x补 + y补 = (x + y)补，(x - y)补 = x补 + (-y)补

计算 1 - 1，即 1 + (-1)
原码：0 0001 + 1 0001 = 1 0010 = -2
反码：0 0001 + 1 1110 = 1 1111 = [1 0000]原 = -0 // 反码还有 +0
补码：0 0001 + 1 1111 = 0 0000 = [0 0000]原 = 0  // 补码的 0 只有一种表示

• 由于补码的 0 只有一种表示，因此对于原码的 -0，规定在补码中表示为其最小数减一，以 8 位补码为例，规定 1000 0000 表示 -128

[0000 0000]补 ~ [0111 1111]补：[0000 0000]原 ~ [0111 1111]原，即 0 ~ 127
[1000 0000]补：原码无法表达（1 1000 0000），规定用来表示 -128
[1000 0001]补 ~ [1111 1111]补：[1111 1111]原 ~ [1000 0001]原，即 -127 ~ -1

• 这个规定能方便地处理溢出情况

127 + 1 => [0111 1111]补 + [0000 0001]补 = [1000 0000]补 = -128
127 + 2 => [0111 1111]补 + [0000 0010]补 = [1000 0001]补 = -127
-128 - 1 => -128 + (-1) => [1000 0000]补 + [1111 1111]补 = [0111 1111]补 = 127
-128 - 2 => -128 + (-2) => [1000 0000]补 + [1111 1110]补 = [0111 1110]补 = 126

• C++ 中使用 ~ 符号按位取反

~4 => 对 4 的补码按位取反
[0 0100]原 => [0 0100]补 => 按位取反 => [1 1011]补
=> 负数补码数值位取反再加 1（或者减 1 得到反码再取反）即为原码，即 [1 0101]原，-5
assert(~4 == -5);

~-4 => 对 -4 的补码按位取反
[1 0100]原 => [1 1100]补 => 按位取反 => [0 0011]补
=> 正数补码等于原码，即 [0 0011]原，3
assert(~-4 == 3);

• 因此，对正数按位取反再加 1 即为其相反数，lowbit 可以直观地使用如下写法

int lowbit(int n) { return n & (-n); }

int main() {
  assert(lowbit(0b10001101) == 1);
  assert(lowbit(0b11011010) == 2);
  assert(lowbit(0b10101100) == 4);
  assert(lowbit(0b10111000) == 8);
  assert(lowbit(0b11010000) == 16);
}

• 对于一个要计算前缀和的数组，需要为其构造一个下标从 1 开始的树状数组

TN 表示以其所在节点为根节点的所有叶子节点的和

                       __________ T8
                      /           /|
                     /           / |
                    /           /  |
                   /           /   |
                  /           /    |
                 /           /     |
        _____ T4            /      |
       /       |           /       |
      /       /|          /       /|
    T2       / |        T6       / |
  /  |      /  |      /  |      /  |
 /   |     /   |     /   |     /   |
T1   |    T3   |    T5   |    T7   |
|    |    |    |    |    |    |    |
A1   A2   A3   A4   A5   A6   A7   A8

T1 = A1
T2 = A1 + A2
T3 = A3
T4 = A1 + A2 + A3 + A4
T5 = A5
T6 = A5 + A6
T7 = A7
T8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

可见，TN 表示的是一个连续子序和，序列结束位置为 AN，包含的元素数量为 lowbit(N)
lowbit(1) = 1
lowbit(2) = 2
lowbit(3) = 1
lowbit(4) = 4
lowbit(5) = 1
lowbit(6) = 2
lowbit(7) = 1
lowbit(8) = 8

查找一个位置的所有前缀和，比如对于 7，前缀和为 A1 + A2 + A3 + A4 + A5 + A6 + A7
=> 初始值为 0，开始累加
=> 加上 T7，T7 包含 lowbit(7) = 1 个元素，因此下一步的位置为 7 - 1 = 6
=> 加上 T6，T6 包含 lowbit(6) = 2 个元素，因此下一步的位置为 6 - 2 = 4
=> 加上 T4，T4 包含 lowbit(4) = 4 个元素，因此下一步的位置为 4 - 4 = 0，结束
=> 结果为 T7 + T6 + T4 = A7 + A5 + A6 + A1 + A2 + A3 + A4 = A1 + A2 + A3 + A4 + A5 + A6 + A7

增减一个位置的值时，需要对其所在节点及其所有祖先节点做相同增减，而 N 的父节点即为 N + lowbit(N)
=> A1 += x
=> T1 += x，lowbit(1) = 1，因此 1 的父节点为 1 + 1 = 2
=> T2 += x，lowbit(2) = 2，因此 2 的父节点为 2 + 2 = 4
=> T4 += x，lowbit(4) = 4，因此 4 的父节点为 4 + 4 = 8
=> T8 += x，lowbit(8) = 8，8 + 8 = 16，超出范围，结束

树的深度为 logN / log2 + 1，因此查找和增减操作的复杂度为 O(log n)

• 树状数组实现如下

class FenwickTree {
 public:
  void init(int n) {
    t.clear();
    t.resize(n);
    t.shrink_to_fit();
  }

  void add(int pos, int value) {
    while (pos < size(t)) {
      t[pos] += value;
      pos += lowbit(pos);
    }
  }

  int prefix_sum(int pos) const {
    int res = 0;
    while (pos) {
      res += t[pos];
      pos -= lowbit(pos);
    }
    return res;
  }

  int range_sum(int from, int to) const {
    return prefix_sum(to) - prefix_sum(from - 1);
  }

  void print_all_prefix_sum() const {
    for (int i = 1; i < size(t); ++i) {
      cout << prefix_sum(i) << ' ';
    }
    cout << endl;
  }

 private:
  int lowbit(int x) const { return x & (-x); }

 private:
  vector<int> t;
};

int main() {
  FenwickTree t;
  vector<int> v{2, 3, 5, 1, 4, 7, 8, 6};
  t.init(size(v) + 1);
  for (int i = 0; i < size(v); ++i) {
    t.add(i + 1, v[i]);
  }
  t.print_all_prefix_sum();           // 2 5 10 11 15 22 30 36
  cout << t.range_sum(2, 3) << endl;  // 8 = 3 + 5
  t.add(3, 10);
  t.print_all_prefix_sum();           // 2 5 20 21 25 32 40 46
  cout << t.range_sum(2, 3) << endl;  // 18
}

• 树状数组的一个应用就是求逆序对数。对于该题，先对 nums 做离散化处理，映射为一个递增序列，倒序遍历 nums，查找 nums[i] 对应于序列中的下标 x，x 即表示有 nums 中有 x 个比 nums[i] 小的数。对树状数组做 add(x + 1, 1) 操作做标记，查找前缀和时，标记过的位置表示在 nums 中遍历过，前缀和即为 nums 中右侧比当前元素小的元素数量

class Solution {
 public:
  vector<int> countSmaller(vector<int>& nums) {
    vector<int> helper{nums};
    sort(begin(helper), end(helper));
    helper.erase(unique(begin(helper), end(helper)), end(helper));
    int sz = size(nums);
    init(sz + 1);
    vector<int> res;
    for (int i = sz - 1; i >= 0; --i) {
      int x = lower_bound(begin(helper), end(helper), nums[i]) - begin(helper);
      res.emplace_back(prefix_sum(x));
      add(x + 1, 1);
    }
    reverse(begin(res), end(res));
    return res;
  }

  void init(int n) {
    t.clear();
    t.resize(n);
    t.shrink_to_fit();
  }

  void add(int pos, int value) {
    while (pos < size(t)) {
      t[pos] += value;
      pos += lowbit(pos);
    }
  }

  int prefix_sum(int pos) const {
    int res = 0;
    while (pos) {
      res += t[pos];
      pos -= lowbit(pos);
    }
    return res;
  }

 private:
  int lowbit(int x) const { return x & (-x); }

 private:
  vector<int> t;
};