树状数组

树状数组或二元索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树.

按照Peter M. Fenwick的说法，正如所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。采用这个想法，我们可将一个前缀和划分成多个子序列的和，而划分的方法与数的2的幂和具有极其相似的方式。一方面，子序列的个数是其二进制表示中1的个数，另一方面，子序列代表的f[i]的个数也是2的幂

code

class fenwickTree
{
public:
    fenwickTree(int size):sums_(size, 0){}; // n + 1
    void update(int index, int delta)
    {
        while (index < sums_.size())
        {
            sums_[index] += delta;
            index += lowBit(index);
        }
    }

    int query(int index)
    {
        int res = 0;
        while (index > 0)
        {
            res += sums_[index];
            index -= lowBit(index);
        }

        return res;
    }

private:
    static inline int lowBit(int i) { return i & (-i); }
    vector<int> sums_;
};

307 solution

class NumArray {
public:
    NumArray(vector<int>& nums):nums_(move(nums)), tree_(nums_.size() + 1){
        // index start from 1
        for (int i = 0; i < nums_.size(); ++i)
            tree_.update(i + 1, nums_[i]);
    }
    
    void update(int index, int val) {
        tree_.update(index + 1, val - nums_[index]);
        nums_[index] = val;
    }
    
    int sumRange(int left, int right) {
        return tree_.query(right + 1) - tree_.query(left);
    }

private:
    vector<int> nums_;
    fenwickTree tree_;
};

315 solution

// 5 2 6 1 -> 2 1 1 0
// 1 6 2 5 -> 0 1 1 2
// 1 2 5 6
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        set<int> oSet(nums.cbegin(), nums.cend());
        unordered_map<int, int> ranks;
        int i = 0;
        // 树状数组是从1开始的
        for (const auto& num : oSet)
            ranks[num] = ++i;

        vector<int> ans;
        fenwickTree tree(oSet.size() + 1);
        for (auto it = nums.rbegin(); it != nums.rend(); ++it)
        {
            ans.push_back(tree.query(ranks[*it] - 1));
            tree.update(ranks[*it], 1);
        }

        return {ans.crbegin(), ans.crend()};
    }
};

reference

https://www.youtube.com/watch?v=WbafSgetDDk

leetcode307

leetcode315