{"id":1482,"date":"2018-01-03T21:27:14","date_gmt":"2018-01-04T05:27:14","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1482"},"modified":"2019-01-29T20:57:34","modified_gmt":"2019-01-30T04:57:34","slug":"307-range-sum-query-mutable","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/307-range-sum-query-mutable\/","title":{"rendered":"\u82b1\u82b1\u9171 307. Range Sum Query – Mutable"},"content":{"rendered":"

\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4\uff0c\u8ba9\u4f60\u6c42\u4e00\u4e2a\u8303\u56f4\u4e4b\u5185\u6240\u6709\u5143\u7d20\u7684\u548c\uff0c\u6570\u7ec4\u5143\u7d20\u53ef\u4ee5\u66f4\u6539\u3002<\/p>\n

Problem:<\/strong><\/p>\n

Given an integer array\u00a0nums<\/i>, find the sum of the elements between indices\u00a0i<\/i>\u00a0and\u00a0j<\/i>\u00a0(i<\/i>\u00a0\u2264\u00a0j<\/i>), inclusive.<\/p>\n

The\u00a0update(i, val)<\/i>\u00a0function modifies\u00a0nums<\/i>\u00a0by updating the element at index\u00a0i<\/i>\u00a0to\u00a0val<\/i>.<\/p>\n

Example:<\/b><\/p>\n

Given nums = [1, 3, 5]\n\nsumRange(0, 2) -> 9\nupdate(1, 2)\nsumRange(0, 2) -> 8\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. The array is only modifiable by the\u00a0update<\/i>\u00a0function.<\/li>\n
  2. You may assume the number of calls to\u00a0update<\/i>\u00a0and\u00a0sumRange<\/i>\u00a0function is distributed evenly.<\/li>\n<\/ol>\n
    Idea:<\/strong><\/p>\n
    Fenwick Tree<\/p>\n
    Solution:<\/strong><\/p>\n
    C++<\/p>\n
    Time complexity:<\/p>\n
    init O(nlogn)<\/p>\n
    query: O(logn)<\/p>\n
    update: O(logn)
    \n
    C++<\/h2>\n
    \n<\/p>\n
    \/\/ Author: Huahua\n\/\/ Running time: 83 ms\nclass FenwickTree {    \npublic:\n    FenwickTree(int n): sums_(n + 1, 0) {}\n    \n    void update(int i, int delta) {\n        while (i < sums_.size()) {\n            sums_[i] += delta;\n            i += lowbit(i);\n        }\n    }\n    \n    int query(int i) const {        \n        int sum = 0;\n        while (i > 0) {\n            sum += sums_[i];\n            i -= lowbit(i);\n        }\n        return sum;\n    }\nprivate:\n    static inline int lowbit(int x) { return x & (-x); }\n    vector<int> sums_;\n};\n\nclass NumArray {\npublic:\n    NumArray(vector<int> nums): nums_(std::move(nums)), tree_(nums_.size()) {\n        for (int i = 0; i < nums_.size(); ++i)\n            tree_.update(i + 1, nums_[i]);\n    }\n    \n    void update(int i, int val) {\n        tree_.update(i + 1, val - nums_[i]);\n        nums_[i] = val;\n    }\n    \n    int sumRange(int i, int j) {\n        return tree_.query(j + 1) - tree_.query(i);\n    }\nprivate:\n    vector<int> nums_;\n    FenwickTree tree_;\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \/\/ Author: Huahua\n\/\/ Running time: 130 ms\nclass NumArray {\n    FenwickTree tree_;\n    int[] nums_;\n    public NumArray(int[] nums) {\n        nums_ = nums;\n        tree_ = new FenwickTree(nums.length);\n        for (int i = 0; i < nums.length; ++i)\n            tree_.update(i + 1, nums[i]);\n    }\n    \n    public void update(int i, int val) {\n        tree_.update(i + 1, val - nums_[i]);\n        nums_[i] = val;\n    }\n    \n    public int sumRange(int i, int j) {\n        return tree_.query(j + 1) - tree_.query(i);\n    }\nclass FenwickTree {\n    int sums_[];\n    public FenwickTree(int n) {\n        sums_ = new int[n + 1];\n    }\n    \n    public void update(int i, int delta) {\n        while (i < sums_.length) {\n            sums_[i] += delta;\n            i += i & -i;\n        }\n    }\n    \n    public int query(int i) {\n        int sum = 0;\n        while (i > 0) {\n            sum += sums_[i];\n            i -= i & -i;\n        }\n        return sum;\n    }\n}\n}<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \"\"\"\nAuthor: Huahua\nRunning time: 192 ms (< 90.00%)\n\"\"\"\nclass FenwickTree:\n    def __init__(self, n):\n        self._sums = [0 for _ in range(n + 1)]\n        \n    def update(self, i, delta):\n        while i < len(self._sums):\n            self._sums[i] += delta\n            i += i & -i\n    \n    def query(self, i):\n        s = 0\n        while i > 0:\n            s += self._sums[i]\n            i -= i & -i\n        return s\n    \nclass NumArray:\n\n    def __init__(self, nums):\n        self._nums = nums\n        self._tree = FenwickTree(len(nums))\n        for i in range(len(nums)):\n            self._tree.update(i + 1, nums[i])\n\n    def update(self, i, val):\n        self._tree.update(i + 1, val - self._nums[i])\n        self._nums[i] = val\n        \n\n    def sumRange(self, i, j):\n        return self._tree.query(j + 1) - self._tree.query(i)\n<\/pre>\n<\/div><\/div>\n\n\n
    Solution 2: Segment Tree<\/h2>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 24 ms\nclass SegmentTreeNode {\npublic:\n  SegmentTreeNode(int start, int end, int sum,\n                  SegmentTreeNode* left = nullptr,\n                  SegmentTreeNode* right = nullptr): \n    start(start),\n    end(end),\n    sum(sum),\n    left(left),\n    right(right){}      \n  SegmentTreeNode(const SegmentTreeNode&) = delete;\n  SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;\n  ~SegmentTreeNode() {\n    delete left;\n    delete right;\n    left = right = nullptr;\n  }\n  \n  int start;\n  int end;\n  int sum;\n  SegmentTreeNode* left;\n  SegmentTreeNode* right;\n};\n\nclass NumArray {\npublic:\n  NumArray(vector nums) {\n    nums_.swap(nums);\n    if (!nums_.empty())\n      root_.reset(buildTree(0, nums_.size() - 1));\n  }\n\n  void update(int i, int val) {\n    updateTree(root_.get(), i, val);\n  }\n\n  int sumRange(int i, int j) {\n    return sumRange(root_.get(), i, j);\n  }\nprivate:\n  vector nums_;\n  std::unique_ptr root_;\n  \n  SegmentTreeNode* buildTree(int start, int end) {  \n    if (start == end) {      \n      return new SegmentTreeNode(start, end, nums_[start]);\n    }\n    int mid = start + (end - start) \/ 2;\n    auto left = buildTree(start, mid);\n    auto right = buildTree(mid + 1, end);\n    auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right);    \n    return node;\n  }\n  \n  void updateTree(SegmentTreeNode* root, int i, int val) {\n    if (root->start == i && root->end == i) {\n      root->sum = val;\n      return;\n    }\n    int mid = root->start + (root->end - root->start) \/ 2;\n    if (i <= mid) {\n      updateTree(root->left, i, val);\n    } else {      \n      updateTree(root->right, i, val);\n    }\n    root->sum = root->left->sum + root->right->sum;\n  }\n  \n  int sumRange(SegmentTreeNode* root, int i, int j) {    \n    if (i == root->start && j == root->end) {\n      return root->sum;\n    }\n    int mid = root->start + (root->end - root->start) \/ 2;\n    if (j <= mid) {\n      return sumRange(root->left, i, j);\n    } else if (i > mid) {\n      return sumRange(root->right, i, j);\n    } else {\n      return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);\n    }\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4\uff0c\u8ba9\u4f60\u6c42\u4e00\u4e2a\u8303\u56f4\u4e4b\u5185\u6240\u6709\u5143\u7d20\u7684\u548c\uff0c\u6570\u7ec4\u5143\u7d20\u53ef\u4ee5\u66f4\u6539\u3002 Problem: Given an integer array\u00a0nums, find the sum of the elements between indices\u00a0i\u00a0and\u00a0j\u00a0(i\u00a0\u2264\u00a0j), inclusive. The\u00a0update(i, val)\u00a0function modifies\u00a0nums\u00a0by updating the element at index\u00a0i\u00a0to\u00a0val. Example: Given…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,126,89],"tags":[204,217,200,201,458],"class_list":["post-1482","post","type-post","status-publish","format-standard","hentry","category-array","category-bit","category-data-structure","tag-fenwick-tree","tag-hard","tag-prefix-sum","tag-range-sum","tag-segment-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1482","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1482"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1482\/revisions"}],"predecessor-version":[{"id":4737,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1482\/revisions\/4737"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1482"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1482"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1482"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}