{"id":786,"date":"2020-03-07T21:13:45","date_gmt":"2020-03-08T05:13:45","guid":{"rendered":"http:\/\/209.126.2.187\/?p=786"},"modified":"2020-07-28T21:36:28","modified_gmt":"2020-07-29T04:36:28","slug":"segment-tree","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/03\/07\/segment-tree\/","title":{"rendered":"Segment Tree"},"content":{"rendered":"\n

Summary<\/h2>\n\n\n\n

In this post, I will introduce several templates for the Segment Tree. Compared to the binary index tree, segment tree is easy to understand, though the codes are longer. I will not introduce 2D Segment Tree in this post.<\/p>\n\n\n\n

Some OJ problems are listed below.<\/p>\n\n\n\n

  1. LC 1157<\/a>: query range majority; update single node;<\/li>
  2. LC 307<\/a>: query range sum; update single node;<\/li><\/ol>\n\n\n\n

    Details<\/h2>\n\n\n\n

    LC 307<\/a><\/h3>\n\n\n\n
    class SegmentTree {\nprivate:\n    vector<int> nums;\n    vector<int> info;\n    int n;\n\n    void build(int left, int right, int root) {\n        if (left > right) {\n            return;\n        } else if (left == right) {\n            info[root] = nums[left];\n        } else {\n            int mid = left + (right - left) \/ 2;\n            build(left, mid, root << 1);\n            build(mid + 1, right, (root << 1) + 1);\n            info[root] = max(info[root << 1], info[(root << 1) + 1]);\n        }\n    }\n\n    void update(int left, int right, int root, int q_index, int val) {\n        if (q_index < left || q_index > right) {\n            return;\n        } else if (left == right) {\n            info[root] += val;\n        } else {\n            int mid = left + (right - left) \/ 2;\n            update(left, mid, root << 1, q_index, val);\n            update(mid + 1, right, (root << 1) + 1, q_index, val);\n            info[root] = max(info[root << 1], info[(root << 1) + 1]);\n        }\n    }\n\n    int query(int left, int right, int root, int q_left, int q_right) {\n        if (q_left > right || q_right < left) {\n            return 0;\n        } else if (q_left <= left && right <= q_right) {\n            return info[root];\n        } else {\n            int mid = left + (right - left) \/ 2;\n            return max(query(left, mid, root << 1, q_left, q_right),\n                       query(mid + 1, right, (root << 1) + 1, q_left, q_right));\n        }\n    }\npublic:\n    SegmentTree(vector<int> const &nums_) : nums(nums_) {\n        n = nums_.size();\n        info.resize(4 * n);\n        build(0, n - 1, 1);\n    }\n    void Update(int q_index, int val) {\n        update(0, n - 1, 1, q_index, val);\n    }\n\n    int Query(int q_left, int q_right) {\n        return query(0, n - 1, 1, q_left, q_right);\n    }\n};<\/code><\/pre>\n\n\n\n
    Query Range Sum & Update Range Nodes<\/h3>\n\n\n\n
    class SegmentTree {\nprivate:\n    vector<int> info;\n    vector<int> tag;\n\n    vector<int> nums;\n    int n;\n\n    void build(int root, int left, int right) {\n        if (left > right) {\n            return;\n        } else if (left == right) {\n            info[root] += nums[left];\n        } else {\n            int mid = left + (right - left) \/ 2;\n            build(root << 1, left, mid);\n            build((root << 1) + 1, mid + 1, right);\n            info[root] = info[root << 1] + info[(root << 1) + 1];\n        }\n    }\n\n    void push_down(int root, int left, int right) {\n        int mid = left + (right - left) \/ 2;\n        info[root << 1] += (mid - left + 1) * tag[root];\n        tag[root << 1] += tag[root];\n        info[(root << 1) + 1] += (right - mid) * tag[root];\n        tag[(root << 1) + 1] += tag[root];\n        tag[root] = 0;\n    }\n\n    void pull_up(int root) {\n        info[root] = info[root << 1] + info[(root << 1) + 1];\n    }\n\n    void update(int root, int left, int right, int q_left, int q_right, int val) {\n        if (right < q_left || left > q_right) {\n            return;\n        } else if (q_left <= left && right <= q_right) {\n            info[root] += (right - left + 1) * val;\n            tag[root] += val;\n        } else {\n            int mid = left + (right - left) \/ 2;\n            push_down(root, left, right);\n            update(root << 1, left, mid, q_left, q_right, val);\n            update((root << 1) + 1, mid + 1, right, q_left, q_right, val);\n            pull_up(root);\n        }\n    }\n\n    int query(int root, int left, int right, int q_left, int q_right) {\n        if (right < q_left || left > q_right) {\n            return 0;\n        } if (q_left <= left && right <= q_right) {\n            return info[root];\n        } else {\n            int mid = left + (right - left) \/ 2;\n            push_down(root, left, right);\n            return query(root << 1, left, mid, q_left, q_right)\n                + query((root << 1) + 1, mid + 1, right, q_left, q_right);\n        }\n    }\n\npublic:\n    SegmentTree(vector<int> const& nums) {\n        this->nums = nums;\n        n = nums.size();\n        info.resize(4 * n);\n        tag.resize(4 * n);\n        build(1, 0, n - 1);\n    }\n\n    void Update(int q_left, int q_right, int val) {\n        update(1, 0, n - 1, q_left, q_right, val);\n    }\n\n    int Query(int q_left, int q_right) {\n        return query(1 ,0, n - 1, q_left, q_right);\n    }\n};<\/code><\/pre>\n\n\n\n
    LC 1157<\/a><\/h3>\n\n\n\n
    \/*\nPre-calculation: O(n * log(n))\nQuery: O(log(n) * log(n))\nSingle Node Update: O(log(n) * log(n))\n*\/\n\ninline int left_child(int root) {\n    return root << 1;\n}\ninline int right_child(int root) {\n    return (root << 1) + 1;\n}\n\nclass MajorityChecker {\nprivate:\n    struct Info {\n        int freq = -1;\n        int num = -1;\n        Info() {}\n        Info(int freq_, int num_) : freq(freq_), num(num_) {}\n        string ToString() {return to_string(num) + \",\" + to_string(freq);}\n    };\n    int n;\n    vector<Info> infos;\n    vector<int> nums;\n    unordered_map<int, vector<int>> num_to_posi;\n    int get_freq(int num, int left, int right) {\n        auto it1 = lower_bound(num_to_posi[num].begin(), num_to_posi[num].end(), left);\n        auto it2 = upper_bound(num_to_posi[num].begin(), num_to_posi[num].end(), right);\n        return distance(it1, it2);\n    }\n\n    void build(int root, int left, int right) {\n        if (left > right) {\n            return; \n        } else if (left == right) {\n            infos[root] = {1, nums[left]};\n        } else {\n            int mid = left + (right - left) \/ 2;\n            build(left_child(root), left, mid);\n            build(right_child(root), mid + 1, right);\n            \/\/ 1 2 1 1\n            if (infos[left_child(root)].num == infos[right_child(root)].num && infos[left_child(root)].num != -1) {\n                infos[root] = {infos[left_child(root)].freq + infos[right_child(root)].freq, infos[left_child(root)].num};\n            } else if (infos[left_child(root)].num != -1 && get_freq(infos[left_child(root)].num, left, right) * 2 > (right - left + 1)) {\n                infos[root] = {get_freq(infos[left_child(root)].num, left, right), infos[left_child(root)].num};\n            } else if (infos[right_child(root)].num != -1 && get_freq(infos[right_child(root)].num, left, right) * 2 > (right - left + 1)) {\n                infos[root] = {get_freq(infos[right_child(root)].num, left, right), infos[right_child(root)].num};\n            } else {\n                infos[root] = {-1, -1};\n            }\n        }\n    }\n\n    Info query(int root, int left, int right, int q_left, int q_right, int thresh) {\n        if (left > q_right || right < q_left) {\n            return {-1, -1};\n        } else if (q_left <= left && right <= q_right) {\n            return infos[root];\n        } else {\n            int mid = left + (right - left) \/ 2;\n            auto left_info = query(left_child(root), left, mid, q_left, q_right, thresh);\n            auto right_info = query(right_child(root), mid + 1, right, q_left, q_right, thresh);\n            \/\/ gather info in range [q_left, q_right]\n            if (left_info.num != -1 && (get_freq(left_info.num, q_left, q_right) * 2 > (q_right - q_left + 1))) {\n                return {get_freq(left_info.num, q_left, q_right), left_info.num};\n            } else if (right_info.num != -1 && (get_freq(right_info.num, q_left, q_right) * 2 > (q_right - q_left + 1))) {\n                return {get_freq(right_info.num, q_left, q_right), right_info.num};\n            } else {\n                return {-1, -1};\n            }\n        }\n    }\n\npublic:\n    void PrintTree() {\n        for (int i = 1; i < 4 * n; ++i) {\n            cout << infos[i].ToString() << \";\";\n        }\n        cout << endl;\n    }\n\n    MajorityChecker(vector<int>& arr) {\n        n = arr.size();\n        infos.resize(n << 2);\n        nums = arr;\n        for (int i = 0; i < arr.size(); ++i) {\n            num_to_posi[arr[i]].push_back(i);\n        }\n        build(1, 0, n - 1);\n    }\n\n    int query(int left, int right, int threshold) {\n        auto info = query(1, 0, n - 1, left, right, threshold);\n        if (info.freq >= threshold) {\n            return info.num;\n        }\n        return -1;\n    }\n};<\/code><\/pre>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    Summary In this post, I will introduce several templates for the Segment Tree. Compared to the binary index tree, segment tree is easy to understand, though the codes are longer. I will not introduce 2D Segment Tree in this post. Some OJ problems are listed below. LC 1157: query range majority; update single node; LC…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,51],"tags":[],"class_list":["post-786","post","type-post","status-publish","format-standard","hentry","category-alg","category-segment-tree"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/786","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=786"}],"version-history":[{"count":14,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/786\/revisions"}],"predecessor-version":[{"id":1520,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/786\/revisions\/1520"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=786"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=786"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=786"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}