Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 983 Reading time ≈ 1 mins.

二分 O(logn) time O(1) space
找『上界』
跟1060. Missing Element in Sorted Array思路接近

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = size(arr), l = 0, r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] - m - 1 >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l + k; // 上界之内已有的正数个数+消失的第k
    }
};

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        arr.push_back(10000); // padding好写code
        for (int i = 0; i < arr.size(); ++i) {
            if (int d = arr[i] - (i + 1); d >= k) { // arr[i]出现在了第i + 1个位置，arr[i]前边本应该有arr[i] - 1个数，结果现在只有i个数，差了d个数，假如d >= k，说明差的第k个数必在这d个数里，因为是第一次出现这种情况，说明一定是从第arr[i]开始往前数第d - k + 1个数
                return arr[i] - (d - k + 1);
            }
        }
        return -1;
    }
};

不padding

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = arr.size();
        for (int i = 0; i < n; ++i) {
            if (int d = arr[i] - (i + 1); d >= k) {
                return arr[i] - (d - k + 1);
            }
        }
        return n + k; // 说明就是第n + k个数
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(n) time O(h) space
每次更新mx和mn，到nullptr时得到根到叶的一条路径上的最大和最小值，只需要求差即可，对于左右两个子树返回上来的不同路径的最大最小值之差，只需要取较大的那个即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val);
    }

    int dfs(TreeNode *root, int mx, int mn) { // 输入从根到当前节点之前的最大和最小值
        return root ? max(dfs(root->left, max(mx, root->val), min(mn, root->val)), dfs(root->right, max(mx, root->val), min(mn, root->val))) : mx - mn;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val); // 初始最大最小都为root即可
    }

    int dfs(TreeNode *root, int mx, int mn) { // 因为是绝对值，所以要维护最大最小两个值
        if (!root) return mx - mn;
        mx = max(mx, root->val);
        mn = min(mn, root->val);
        return max(dfs(root->left, mx, mn), dfs(root->right, mx, mn));
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class RandomizedCollection {
public:
    /** Initialize your data structure here. */
    RandomizedCollection() {
        srand(time(NULL));
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        bool res = m.find(val) == m.end();
        m[val].push_back(v.size());
        v.emplace_back(val, m[val].size() - 1);
        return res;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if (!m.count(val)) return false;
        m[v.back().first][v.back().second] = m[val].back();
        v[m[val].back()] = v.back();
        v.pop_back();
        m[val].pop_back();
        if (m[val].empty()) m.erase(val); // 切记如果m[val]空了要从m中删掉！！
        return true;
    }

    /** Get a random element from the collection. */
    int getRandom() {
        return v.empty() ? 0 : v[rand() % v.size()].first;
    }

    unordered_map<int, vector<int>> m; // 添加删除O(1)所以要用unordered容器，unordered_map可保存更多信息，这里对应每个key存v中所有该key的下标
    vector<pair<int, int>> v; // 数组不是只存val，还要存val所在m中的下标集合的下标，即m[v[i].first][v[i].second] = i，v[i].first是val，v[i].second是m[val]对应的数组的下标，通过该下标可以得到val在v中的下标，这么做是因为每次删除以后被修改的数在m中的下标数组不一定是有序的
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * bool param_1 = obj.insert(val);
 * bool param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

抛开题目，根据权重（个数）返回value的另一种方法是手撸一个支持dup的bst，每个node包含左右子树+自身的权重和，利用230. Kth Smallest Element in a BST的followup的思路，找指定node即可

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

backtracking O(4n - m) time O(n - m) space
n是所有cell的个数 m是障碍的个数
尝试在每个方向上clean一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * class Robot {
 *   public:
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     bool move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     void turnLeft();
 *     void turnRight();
 *
 *     // Clean the current cell.
 *     void clean();
 * };
 */
class Solution {
public:
    vector<pair<int, int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    unordered_set<string> s;
    int r = 0, c = 0, d = 0;
    void cleanRoom(Robot& robot) {
        auto k = to_string(r) + " " + to_string(c);
        if (s.count(k)) return;
        s.insert(k);
        robot.clean();
        for (int i = 0; i < 4; ++i) { // 每一个cell尝试四个方向
            if (robot.move()) { // 任何一个方向能前进的话
                auto [dr, dc] = dirs[d];
                r += dr;
                c += dc;
                cleanRoom(robot); // 尝试在这个方向上clean（有可能已经clean过，则回退）
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
                r -= dr;
                c -= dc;
            }
            robot.turnRight(); // 尝试下一个方向
            d = (d + 1) % 4;
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

O(n) 朴素解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy_head(0), *prev = &dummy_head;
        prev->next = head;
        for (auto curr = head; curr; curr = curr->next) {
            if (curr->val == val) {
                prev->next = curr->next;
            } else {
                prev = curr;
            }
        }
        return dummy_head.next;
    }
};

O(n)二级指针法
一般一个节点分两部分，数据和next指针，各自有不同的地址（占用不同的内存空间），我们要做的是改变要删除的节点的前驱节点的next指针的值，如果当前节点不是要删除的目标节点，我们取next指针的地址保存起来，即list = &(*list)->next;，下次循环的时候，我们是站在前驱节点的位置来检查前驱节点的后继节点是不是要被删除的目标节点，如果是的话，直接修改这个『next』指针值，即*list = (*list)->next;，相当于node->next = node->next->next;，其中node->next是要被删除的目标节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode **list = &head;

        while (*list)
        {
            if ((*list)->val == val)
            {
                *list = (*list)->next; // 因为之前保存了前驱节点的next指针信息，所以可以直接修改前驱节点的next指针的值为当前节点的后继节点
            } else {
                list = &(*list)->next; // 保存的其实是当前节点的next指针信息，而不是下一个节点
            }
        }

        return head;
    }
};

O(n)递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head) return nullptr;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 369 Reading time ≈ 1 mins.

O(n) time O(n) space
把0改成-1，题目变成找最长的和为0的连续子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> m;
        int n = nums.size(), res = 0, diff = 0;
        m[0] = -1;
        for (int i = 0; i < n; ++i) {
            diff += (nums[i] == 1 ? 1 : -1);
            if (m.count(diff)) {
                res = max(res, i - m[diff]);
            } else {
                m[diff] = i;
            }
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 582 Reading time ≈ 1 mins.

二分+two pointers O(k+logn) time
两个指针分别向左右移，最后把两个指针之间的数返回即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        auto it = upper_bound(begin(arr), end(arr), x); // lower_bound也行
        int n = arr.size(), r = it == end(arr) ? n - 1 : it - begin(arr), l = r - 1;
        while (k-- > 0) {
            if (l < 0) {
                ++r;
            } else if (r >= n) {
                --l;
            } else {
                if (x - arr[l] <= arr[r] - x) { // arr[l] < x <= arr[r]
                    --l;
                } else {
                    ++r;
                }
            }
        }
        return vector<int>(begin(arr) + l + 1, begin(arr) + r); // 因为l和r都会多走一步，所以l要回退一步，r正好不用
    }
};

Posted on Edited on Disqus:
Symbols count in article: 5.4k Reading time ≈ 5 mins.

这道题用bellman-ford就可以了
每次relax的时候存前后结点，最后倒推一遍即可输出路径
O((e+n)logn) time push共e次 pop共n次
改进后的dijkstra，记录所有点k个stop以内的最小费用和（普通的dijkstra是记录所有点的全局最小费用和）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> graph(n, vector<int>(n, 1e7)); // 用邻接矩阵存图
        for (const auto &f : flights) {
            graph[f[0]][f[1]] = f[2];
        }
        ++K; // 这里K个stop不包括起点和终点，所以要++方便操作，表示K次飞行
        vector<vector<int>> dist(n, vector<int>(K + 1, 1e7)); // cache所有点k次飞行以内的最优解
        auto cmp = [](const vector<int> &lhs, const vector<int> &rhs) {return lhs[2] > rhs[2];};
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp); // 用堆记录每个点每次飞行的可能解，这里需要单独存一份开销dist因为把dist传到cmp里不能在堆上即时反应出来
        q.push({src, 0, 0}); // 从src飞到src，0次飞行，开销是0
        // dist[src][0] = 0; // 可写可不写
        while (!q.empty()) {
            auto v = q.top(); q.pop();
            int u = v[0], k = v[1], d = v[2];
            if (u == dst) return d; // 因为堆肯定是最优解（最小费用和）在前，所以第一次碰到dst一定就是最优解
            if (k == K) continue; // 已经达到上限，不propagate了，否则relax时dist[i][k + 1]会outofbound
            for (int i = 0; i < n; ++i) {
                if (dist[i][k + 1] > d + graph[u][i]) { // relax
                    dist[i][k + 1] = d + graph[u][i];
                    q.push({i, k + 1, dist[i][k + 1]});
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    using tiii = tuple<int, int, int>;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<pair<int, int>>> g(n);
        for (const auto &f : flights) {
            g[f[0]].emplace_back(f[1], f[2]);
        }
        vector<vector<int>> dist(n, vector<int>(K + 1, INT_MAX));
        priority_queue<tiii, vector<tiii>, greater<tiii>> q;
        q.emplace(0, src, 0);
        dist[src][0] = 0;
        while (!q.empty()) {
            auto [cost, u, k] = q.top(); q.pop();
            if (u == dst) return cost;
            if (k == K) continue;
            for (auto [v, c] : g[u]) {
                if (cost + c < dist[v][k + 1]) {
                    dist[v][k + 1] = cost + c;
                    q.emplace(cost + c, v, k + 1);
                }
            }
        }
        return -1;
    }
};

没做剪枝的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    using tiii = tuple<int, int, int>;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<pair<int, int>>> g(n);
        for (const auto &f : flights) {
            g[f[0]].emplace_back(f[1], f[2]);
        }
        priority_queue<tiii, vector<tiii>, greater<tiii>> q;
        q.emplace(0, src, 0);
        while (!q.empty()) {
            auto [cost, u, k] = q.top(); q.pop();
            if (u == dst) return cost;
            if (k == K) continue;
            for (auto [v, c] : g[u]) {
                q.emplace(cost + c, v, k + 1);
            }
        }
        return -1;
    }
};

bellman-ford变种 O(K*E) time O(VK) space
因为最多只能K个stop，所以relax K次就可以了
每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过 |V|-1 条边，所以可知贝尔曼-福特算法所得为最短路径。
K个stop转换成K+1次飞行，直飞就是1次飞行
f[i][j]表示最多i次飞行从src到达j的最小开销
这里所有的f[i][src] = 0 where 0 <= i <= K + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> d(K + 2, vector<int>(n, 1e7));
        d[0][src] = 0; // 0次飞行哪也去不了，肯定为0
        for (int i = 1; i <= K + 1; ++i) {
            d[i][src] = 0; // 任何次数的飞行都是回到原点
            for (const auto &f : flights) {
                d[i][f[1]] = min(d[i][f[1]], d[i - 1][f[0]] + f[2]); // 进行relax
            }
        }
        return d[K + 1][dst] == 1e7 ? -1 : d[K + 1][dst];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<int>> d(K + 1, vector<int>(n, 1e7));
        d[0][src] = 0;
        for (int i = 1; i <= K; ++i) {
            d[i][src] = 0;
            for (const auto &f : flights) {
                d[i][f[1]] = min(d[i][f[1]], d[i - 1][f[0]] + f[2]);
            }
        }
        return d[K][dst] == 1e7 ? -1 : d[K][dst];
    }
};

滚动数组空间优化以后的bellman-ford变种 O(K*E) time O(V) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<int>> d(2, vector<int>(n, 1e7));
        d[0][src] = 0;
        for (int i = 1; i <= K; ++i) {
            d[i & 1][src] = 0;
            for (const auto &f : flights) {
                d[i & 1][f[1]] = min(d[i & 1][f[1]], d[(i - 1) & 1][f[0]] + f[2]);
            }
        }
        return d[K & 1][dst] == 1e7 ? -1 : d[K & 1][dst];
    }
};

加入剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<int>> d(K + 1, vector<int>(n, 1e7));
        d[0][src] = 0;
        for (int i = 1; i <= K; ++i) {
            d[i][src] = 0;
            bool changed = false;
            for (const auto &f : flights) {
                if (d[i - 1][f[0]] + f[2] < d[i][f[1]]) {
                    d[i][f[1]] = d[i - 1][f[0]] + f[2];
                    changed = true;
                }
            }
            if (!changed) break;
        }
        return d[K][dst] == 1e7 ? -1 : d[K][dst];
    }
};

BFS 如果有圈的话不如dijkstra 比如[[0, 1, 1], [1, 0, 1], [1, 2, 1], [2, 1, 1], [2, 3, 1], [3, 2, 1], [0, 3, 2]] 1stop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<pair<int, int>>> g(n);
        for (const auto &f : flights) {
            g[f[0]].emplace_back(f[1], f[2]);
        }
        queue<pair<int, int>> q{{{src, 0}}};
        int k = 0, res = INT_MAX;
        while (!q.empty() && k <= K) {
            for (int i = q.size(); i > 0; --i) {
                auto [u, cost] = q.front(); q.pop();
                if (u == dst) {
                    res = min(res, cost);
                }
                for (auto [v, c] : g[u]) {
                    if (cost + c < res) {
                        q.emplace(v, cost + c);
                    }
                }
            }
            ++k;
        }
        return res == INT_MAX ? -1 : res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

dijkstra’s algorithm+heap O(NlogN + E) time O(N + E) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<int> d(N + 1, INT_MAX);
        d[0] = d[K] = 0;
        vector<vector<pair<int, int>>> g(N + 1);
        for (const auto &t : times) {
            g[t[0]].emplace_back(t[1], t[2]);
        }
        auto cmp = [&d](int a, int b) { return d[a] == d[b] ? a < b : d[a] < d[b]; }; // 注意当d[a] == d[b]的时候set无法区分，所以只会保留一个数
        set<int, decltype(cmp)> q(cmp);
        q.insert(K);
        while (!q.empty()) {
            int u = *begin(q); q.erase(begin(q));
            for (auto [v, w] : g[u]) {
                if (d[u] + w < d[v]) {
                    q.erase(v);
                    d[v] = d[u] + w;
                    q.insert(v);
                }
            }
        }
        int res = 0;
        for (int x : d) {
            if (x == INT_MAX) return -1;
            res = max(res, x);
        }
        return res;
    }
};
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 6.1k Reading time ≈ 6 mins.

常规线段树
指针版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class NumArray {
    struct Node {
        Node(int b, int e, int val, Node *l = nullptr, Node *r = nullptr)
            : b(b), e(e), val(val), l(l), r(r) {
        }

        int b, e, val;
        Node *l, *r;
    };
public:
    NumArray(vector<int>& nums) {
        if (nums.empty()) return;
        n = nums.size();
        root = build(nums, 0, n - 1);
    }

    Node *build(const vector<int> &A, int l, int r) {
        if (l == r) {
            return new Node(l, r, A[l]);
        } else {
            int m = l + (r - l) / 2;
            auto tl = build(A, l, m);
            auto tr = build(A, m + 1, r);
            return new Node(l, r, tl->val + tr->val, tl, tr);
        }
    }

    void update(int i, int val) {
        update(root, i, val);
    }

    void update(Node *p, int i, int val) {
        if (p->b == i && p->e == i) {
            p->val = val;
        } else {
            int m = p->b + (p->e - p->b) / 2;
            if (i <= m) {
                update(p->l, i, val);
            } else {
                update(p->r, i, val);
            }
            p->val = p->l->val + p->r->val;
        }
    }

    int sumRange(int i, int j) {
        return query(root, i, j);
    }

    int query(Node *p, int l, int r) {
        if (l > r) return 0;
        if (p->b == l && p->e == r) return p->val;
        int m = p->b + (p->e - p->b) / 2;
        return query(p->l, l, min(m, r)) + query(p->r, max(l, m + 1), r);
    }

    int n;
    Node *root = nullptr;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

数组版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class NumArray {
public:
    NumArray(vector<int>& nums) {
        if (nums.empty()) return;
        n = nums.size();
        tree.resize(4 * n); // 开大小为4n的数组
        build(1, nums, 0, n - 1);
    }

    void build(int v, const vector<int> &A, int l, int r) {
        if (l == r) {
            tree[v] = A[l];
        } else {
            int m = l + (r - l) / 2;
            build(v * 2, A, l, m);
            build(v * 2 + 1, A, m + 1, r);
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
    }

    void update(int i, int val) {
        update(1, 0, n - 1, i, val);
    }

    void update(int v, int l, int r, int p, int val) {
        if (l == r) {
            tree[v] = val;
        } else {
            int m = l + (r - l) / 2;
            if (p <= m) {
                update(v * 2, l, m, p, val);
            } else {
                update(v * 2 + 1, m + 1, r, p, val);
            }
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
    }

    int sumRange(int i, int j) {
        return query(1, 0, n - 1, i, j);
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (tl == l && tr == r) return tree[v];
        int m = tl + (tr - tl) / 2;
        return query(v * 2, tl, m, l, min(m, r)) + query(v * 2 + 1, m + 1, tr, max(m + 1, l), r);
    }

    int n;
    vector<int> tree;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

zkw segment tree O(n) constructor O(logn) update O(logn) sum O(n) space
只支持bottom-up的题，top-down的题一律用常规线段树做
用数组来表示线段树
原始数组为[1, 2, 3, 4]则数组为[0, 10, 3, 7, 1, 2, 3, 4]，
原始数组为[1, 2, 3]则数组为[0, 6, 5, 1, 2, 3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class NumArray {
public:
    NumArray(vector<int>& nums) {
        n = nums.size();
        tree.resize(2 * n); // 开大小为2n的数组
        copy(begin(nums), end(nums), begin(tree) + n); // 把原始数组的n个数放在最后
        for (int i = n - 1; i > 0; --i) { // 自底向上累加
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    void update(int i, int val) {
        i += n;
        for (int d = val - tree[i]; i > 0; i >>= 1) { // 从叶节点开始用新旧数差值d自底向上来更新线段树
            tree[i] += d;
        }
    }

    int sumRange(int i, int j) {
        int res = 0;
        for (i += n, j += n; i <= j; i >>= 1, j >>= 1) { // 分别找到两个叶节点的位置，自底向上『递归』
            if (i & 1) { // 如果左边界是奇数，则证明是一个右子树，直接累加并右移一个节点，如果左边界是偶数，则证明是一个左子树，其父节点是左右两子树之和，继续向上递归即可
                res += tree[i++];
            }
            if ((j & 1) == 0) { // 如果右边界是偶数，则证明是一个左子树，直接累加并左移一个节点，如果右边界是奇数，则证明是一个右子树，其父节点是左右两子树之和，继续向上递归即可
                res += tree[j--];
            }
        }
        return res;
    }

    int n;
    vector<int> tree;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

树状数组
constructor O(nlogn)
update O(logn)
sumRange O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class NumArray {
public:
    NumArray(vector<int> nums) {
        v = nums;
        int n = nums.size();
        BIT.resize(n + 1);
        for (int i = 0; i < n; ++i) {
            helper(i, nums[i]);
        }
    }

    int query(int i) {
        int sum = 0;
        ++i;
        while (i > 0) {
            sum += BIT[i];
            i -= (i & -i);
        }
        return sum;
    }

    void update(int i, int val) {
        helper(i, val - v[i]);
        v[i] = val;
    }

    void helper(int i, int val) {
        ++i;
        while (i < BIT.size()) {
            BIT[i] += val;
            i += (i & -i);
        }
    }

    int sumRange(int i, int j) {
        return query(j) - query(i - 1);
    }

    vector<int> BIT, v;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

二维树状数组求区间和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>

using namespace std;

struct Solution {
	Solution(const vector<vector<int>> &mtx) : mtx(mtx) {
		int n = mtx.size(), m = mtx[0].size();
		BIT.resize(n + 1, vector<int>(m + 1));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				helper(i, j, mtx[i][j]);
			}
		}
	}

	int query(int i, int j) {
		++i, ++j;
		int sum = 0;
		while (i > 0) {
			int t = j; // 注意要保存j因为每次内循环要用原值
			while (t > 0) {
				sum += BIT[i][t];
				t -= (t & -t);
			}
			i -= (i & -i);
		}
		return sum;
	}

	int query(int uli, int ulj, int lri, int lrj) {
		return query(lri, lrj) - query(lri, ulj - 1) - query(uli - 1, lrj) + query(uli - 1, ulj - 1); // 注意跟一维的不一样，不能只减左上角还有两边的矩阵和也要减
	}

	void helper(int i, int j, int val) {
		++i, ++j;
		while (i < BIT.size()) {
			int t = j;
			while (t < BIT[i].size()) {
				BIT[i][t] += val;
				t += (t & -t);
			}
			i += (i & -i);
		}
	}

	void update(int i, int j, int val) {
		helper(i, j, val - mtx[i][j]);
		mtx[i][j] = val;
	}

	vector<vector<int>> mtx, BIT;
};

int main() {
	// your code goes here
	vector<vector<int>> mtx = {
		{3, 2, 2, 8, 1, 6, 4},
		{4, 2, 7, 0, 2, 8, 1},
		{2, 9, 1, 6, 5, 5, 5},
		{2, 7, 4, 4, 1, 4, 8},
		{0, 4, 7, 1, 2, 5, 8},
		{7, 2, 8, 2, 1, 6, 9}
	};
	Solution s(mtx);
	cout << s.query(0, 0, 5, 6) << endl;
	cout << s.query(2, 3, 3, 5) << endl;
	s.update(4, 2, 8);
	cout << s.query(0, 0, 5, 6) << endl;
	cout << s.query(1, 2, 4, 5) << endl;

	return 0;
}