{"id":2195,"date":"2016-09-22T21:42:18","date_gmt":"2016-09-22T13:42:18","guid":{"rendered":"http:\/\/boweihe.me\/?p=2195"},"modified":"2016-09-22T21:42:18","modified_gmt":"2016-09-22T13:42:18","slug":"%e7%ba%bf%e6%ae%b5%e6%a0%91%e7%9a%84%e9%80%92%e5%bd%92%e5%ae%9e%e7%8e%b0%ef%bc%88%e7%bf%bb%e8%af%91%ef%bc%89","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2195","title":{"rendered":"\u7ebf\u6bb5\u6811\u7684\u9012\u5f52\u5b9e\u73b0 1 of 2: \u6784\u9020\u3001\u67e5\u8be2\u53ca\u66f4\u65b0\uff08\u7ffb\u8bd1\uff09"},"content":{"rendered":"

\u672c\u6587\u7ffb\u8bd1\u81eahttps:\/\/leetcode.com\/articles\/recursive-approach-segment-trees-range-sum-queries-lazy-propagation\/<\/a>\uff0c\u5982\u6709\u4fb5\u6743\u8bf7\u76f4\u63a5Email\u6211<\/p><\/blockquote>\n

\u7b80\u4ecb<\/h3>\n

\u4ec0\u4e48\u662f\u7ebf\u6bb5\u6811(Segment Tree)<\/h4>\n

\u7ebf\u6bb5\u6811\u662f\u4e00\u79cd\u4e8c\u53c9\u6811\uff0c\u6811\u4e2d\u7684\u6bcf\u4e00\u4e2a\u8282\u70b9\u4ee3\u8868\u4e00\u6bb5\u533a\u95f4\u3002\u901a\u5e38\u4e00\u4e2a\u8282\u70b9\u50a8\u5b58\u8fd9\u4e2a\u533a\u95f4\u7684\u4e00\u4e2a\u6216\u591a\u4e2a\u5c5e\u6027\u7528\u4e8e\u540e\u7eed\u67e5\u8be2\u3002
\n

\"What
What is a Segment Tree<\/figcaption><\/figure><\/p>\n

\u4e3a\u4ec0\u4e48\u8981\u4f7f\u7528\u7ebf\u6bb5\u6811\uff08\u5b83\u7684\u7279\u70b9\u662f\u4ec0\u4e48\uff09?<\/h4>\n

\u8bb8\u591a\u95ee\u9898\u9700\u8981\u6211\u4eec\u7ed9\u51fa\u6570\u636e\u96c6\u5728\u67d0\u4e2a\u533a\u95f4\u6216\u8005\u7247\u6bb5\u5185\u7684\u67e5\u8be2\u7ed3\u679c\u3002\u7279\u522b\u662f\u5f53\u51fa\u73b0\u5927\u91cf\u3001\u91cd\u590d\u7684\u67e5\u8be2\u65f6\uff0c\u8fd9\u7c7b\u64cd\u4f5c\u4f1a\u53d8\u5f97\u5197\u957f\u6216\u7f13\u6162\u3002\u4e00\u4e2a\u7ebf\u6bb5\u6811\u53ef\u4ee5\u8ba9\u6211\u4eec\u5728\u5bf9\u6570\u7ea7\u65f6\u95f4\u590d\u6742\u5ea6\u5185\u5f97\u5230\u8fd9\u7c7b\u95ee\u9898\u7684\u67e5\u8be2\u7ed3\u679c\u3002
\n\u7ebf\u6bb5\u6811\u5728\u8ba1\u7b97\u96c6\u5408\u5b66\u3001GIS<\/a>\u7b49\u9886\u57df\u6709\u76f8\u5173\u5e94\u7528\u3002\u4f8b\u5982\uff0c\u6211\u4eec\u53ef\u80fd\u4f1a\u5728\u8ddd\u79bb\u67d0\u4e2a\u4e2d\u5fc3\u70b9\/\u539f\u70b9\u9644\u8fd1\u4e00\u6bb5\u8ddd\u79bb\u7684\u7a7a\u95f4\u8303\u56f4\u5185\u6709\u5927\u91cf\u7684\u53c2\u8003\u70b9\u3002\u5047\u8bbe\u6211\u4eec\u9700\u8981\u67e5\u8be2\u8ddd\u79bb\u539f\u70b9\u6307\u5b9a\u8ddd\u79bb\u8303\u56f4\u5185\u7684\u76f8\u5173\u53c2\u8003\u70b9\u3002\u4e00\u4e2a\u666e\u901a\u7684\u67e5\u8be2\u8868\u9700\u8981\u7ebf\u6027\u9636\u7684\u65f6\u95f4\u6765\u626b\u63cf\u6240\u6709\u7684\u70b9\u6216\u6240\u6709\u53ef\u80fd\u7684\u8ddd\u79bb\uff08\u60f3\u4e00\u4e0bhash map\uff09\u3002\u7ebf\u6bb5\u6811\u5141\u8bb8\u6211\u4eec\u5728\u5bf9\u6570\u65f6\u95f4\u5185\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\uff0c\u5e76\u4e14\u62e5\u6709\u66f4\u5c11\u7684\u7a7a\u95f4\u6d88\u8017\u3002\u8fd9\u7c7b\u95ee\u9898\u88ab\u79f0\u4f5c Planar Range Searching<\/a>\u3002\u9ad8\u6548\u89e3\u51b3\u8fd9\u7c7b\u95ee\u9898\u662f\u81f3\u5173\u91cd\u8981\u7684\uff0c\u7279\u522b\u662f\u5728\u5904\u7406\u90a3\u4e9b\u5feb\u901f\u53d8\u6362\u3001\u65e0\u6cd5\u9884\u77e5\u7684\u52a8\u6001\u6570\u636e\u65f6\uff08\u4f8b\u5982\uff0c\u4e00\u4e2a\u7a7a\u7ba1\u96f7\u8fbe\u7cfb\u7edf\uff09\u3002
\n\u672c\u6587\u7a0d\u540e\u4f1a\u89e3\u51b3\u533a\u95f4\u548c\u67e5\u8be2\u95ee\u9898\uff08Range Sum Query Problem\uff09<\/a>\u4f5c\u4e3a\u4e00\u4e2a\u4f8b\u5b50\uff0c\u501f\u6b64\u8bf4\u660e\u7ebf\u6bb5\u6811\u662f\u5982\u4f55\u8282\u7701\u7a7a\u95f4\u53ca\u5b9e\u65f6\u4ee3\u4ef7\u3002
\n\"\"
\n\u6211\u4eec\u5c06\u4f1a\u4f7f\u7528\u4e0a\u56fe\u4f5c\u4e3a\u4e00\u4e2a\u5b9e\u4f8b\u6765\u4ecb\u7ecd\u7528\u4e8e\u201c\u533a\u95f4\u548c\u67e5\u8be2\u201d\u7684\u7ebf\u6bb5\u6811\u5b83\u957f\u4ec0\u4e48\u6837\uff0c\u4ee5\u53ca\u6709\u4f55\u7279\u6027\u3002<\/p>\n

\u5982\u4f55\u751f\u6210\u4e00\u4e2a\u7ebf\u6bb5\u6811<\/h4>\n

\u6211\u4eec\u5c06\u6570\u636e\u4fdd\u5b58\u5728\u5927\u5c0f\u4e3a[latex]n[\/latex]\u7684\u6570\u7ec4arr[]<\/span>\u00a0\u4e2d\u3002<\/p>\n

    \n
  1. \u7ebf\u6bb5\u6811\u6811\u7684\u6839\u901a\u5e38\u8868\u793a\u6574\u4e2a\u6570\u636e\u7684\u533a\u95f4\u8303\u56f4\uff0c\u5373arr[0:n-1]<\/span>\u00a0\uff1b<\/li>\n
  2. \u6811\u7684\u6bcf\u4e00\u4e2a\u53f6\u8282\u70b9\u8868\u793a\u5355\u4e2a\u5143\u7d20\uff08\u6216\u53ea\u6709\u4e00\u4e2a\u5143\u7d20\u7684\u533a\u95f4\uff09\u3002\u56e0\u6b64\u53f6\u8282\u70b9\u8868\u793a\u7684\u6570\u503c\u4e3aarr[0]<\/span>\u00a0,arr[1]<\/span>\u00a0\u76f4\u81f3arr[n-1]<\/span>\u00a0\uff1b<\/li>\n
  3. \u6811\u7684\u975e\u53f6\u8282\u70b9\u8868\u793a\u5176\u5b50\u8282\u70b9\u5408\u5e76(merge\/union)<\/strong>\u540e\u7684\u7ed3\u679c\uff1b<\/li>\n
  4. \u6bcf\u4e00\u4e2a\u5b50\u8282\u70b9\u90fd\u80fd\u8868\u793a\u5176\u7236\u8282\u70b9\u4e00\u534a\u7684\u533a\u95f4\u8303\u56f4\uff1b<\/li>\n<\/ol>\n

    \u4e00\u4e2a\u5305\u542b[latex]n[\/latex]\u4e2a\u5143\u7d20\u8303\u56f4\u7684\u7ebf\u6bb5\u6811\u53ef\u4ee5\u7528\u4e00\u4e2a[latex]\\approx 4 * n[\/latex]\u5927\u5c0f\u7684\u6570\u7ec4\u8868\u793a\u3002\uff08\u5176\u539f\u56e0\u5728StackOverflow<\/a>\u4e0a\u6709\u8be6\u5c3d\u7684\u8ba8\u8bba\u3002\u5982\u679c\u4f60\u4ecd\u4e0d\u76f8\u4fe1\uff0c\u6ca1\u5173\u7cfb\uff0c\u6211\u4eec\u7a0d\u540e\u4f1a\u8fdb\u4e00\u6b65\u8ba8\u8bba\u3002\uff09<\/p>\n

    \u600e\u4e48\uff08\u7528\u6570\u7ec4\uff09\u5b58\u5462\uff1f<\/h5>\n

    \u601d\u8def\u5f88\u7b80\u5355\uff1a\u4e00\u4e2a\u7d22\u5f15\u53f7\u4e3a[latex]i[\/latex]\u7684\u8282\u70b9\uff0c\u4ed6\u7684\u5b50\u8282\u70b9\u7684\u7d22\u5f15\u53f7\u4e3a[latex](2*i+1)[\/latex]\u4ee5\u53ca[latex](2*i+2)[\/latex].
    \n\"\"
    \n\u5728\u4f7f\u7528\u9012\u5f52\u65b9\u6cd5\u6784\u5efa\u65f6\uff0c\u7ebf\u6bb5\u6811\u975e\u5e38\u76f4\u89c2\u4e14\u5bb9\u6613\u4f7f\u7528\u3002<\/p>\n

    \u7ebf\u6bb5\u6811\u7684\u9012\u5f52\u65b9\u6cd5<\/h3>\n

    \u6211\u4eec\u5c06\u4f7f\u7528\u6570\u7ec4tree[]<\/span>\u00a0\u6765\u4fdd\u5b58\u7ebf\u6bb5\u6811\uff08\u75280\u503c\u521d\u59cb\u5316\uff09\u7684\u8282\u70b9\u5c5e\u6027\u3002\u4ee5\u4e0b\u662f\u5177\u4f53\u7684\u5b58\u50a8\u65b9\u6848\uff08\u4f7f\u7528\u4ee50\u5f00\u59cb\u7684\u7d22\u5f15\u53f7\uff09\uff1a<\/p>\n

      \n
    • \u6811\u7684\u6839\u8282\u70b9\u7d22\u5f15\u4e3a0\uff0c\u5373tree[0]<\/span><\/li>\n
    • \u8282\u70b9tree[i]<\/span>\u00a0\u7684\u5b50\u8282\u70b9\u5b58\u50a8\u5728tree[2*i+1]<\/span>\u00a0\u53catree[2*i+2]<\/span>\u00a0\u4e2d<\/li>\n
    • \u5f53\u6570\u7ec4\u5143\u7d20\u6570\u91cf\u4e0d\u662f2\u7684k\u6b21\u65b9\uff08\u59822,4,8,16,32…\uff09\u65f6\uff0c\u7528\u00a00\u00a0<\/span>\u00a0\u6216null<\/span>\u00a0\u586b\u5145\u4e0d\u8db3\u7684\u5143\u7d20\u503c<\/li>\n<\/ul>\n
      \u6211\u4eec\u771f\u7684\u9700\u8981\u75280\u586b\u5145\u4e48?<\/h5>\n

      \u4e0d\u5b8c\u5168\u662f\u3002\u53ea\u662f\u9700\u8981\u4fdd\u8bc1tree[]\u8db3\u591f\u5927\uff0c\u5e76\u4e14\u521d\u59cb\u503c\u90fd\u662f0\uff0c\u800c\u4e14\u4e0d\u9700\u8981\u62c5\u5fc3\u989d\u5916\u7684\u53f6\u8282\u70b9\u6ca1\u6709\u88ab\u5904\u7406\u8fc7\u3002<\/p>\n

        \n
      • \u53f6\u8282\u70b9\u7684\u7d22\u5f15\u8303\u56f4\u662f[latex]2^k-1[\/latex]\u5230[latex]2^(k+1)-2[\/latex]<\/li>\n<\/ul>\n

        \"\"
        \n\u6211\u4eec\u53ea\u9700\u8981\u4e0b\u5217\u4e09\u4e2a\u65b9\u6cd5\uff1a<\/p>\n

        1.\u6839\u636e\u7ed9\u5b9a\u6570\u636e\u6784\u9020\u7ebf\u6bb5\u6811<\/h4>\n
        void buildSegTree(vector<int>& arr, int treeIndex, int lo, int hi)\n{\n    if (lo == hi) {                 \/\/ \u53f6\u8282\u70b9. \u5728\u91cc\u9762\u5b58\u50a8\u6570\u503c.\n        tree[treeIndex] = arr[lo];\n        return;\n    }\n    int mid = lo + (hi - lo) \/ 2;   \/\/ \u5b50\u8282\u70b9\uff0c\u9012\u5f52\u8fdb\u4e00\u5c42.\n    buildSegTree(arr, 2 * treeIndex + 1, lo, mid);\n    buildSegTree(arr, 2 * treeIndex + 2, mid + 1, hi);\n    \/\/ \u5408\u5e76\u6784\u9020\u7ed3\u679c\n    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);\n}\n\/\/ call this method as buildSegTree(arr, 0, 0, n-1);\n\/\/ Here arr[] is input array and n is its size.<\/pre>\n
        \u8be5\u65b9\u6cd5\u81ea\u4e0b\u800c\u4e0a\u5730\u6784\u9020\u6574\u4e2atree<\/span>\u00a0\u3002\u5f53\u6ee1\u8db3\u6761\u4ef6[latex]lo=hi[\/latex]\u65f6\uff0c\u6211\u4eec\u5904\u7406\u7684\u533a\u95f4\u53ea\u5305\u542b\u5355\u4e2a\u5143\u7d20\uff08\u5373arr[lo]<\/span>\u00a0\uff09\u3002\u8fd9\u5c31\u662f\u6811\u7684\u53f6\u8282\u70b9\u3002\u4f59\u4e0b\u7684\u975e\u53f6\u8282\u70b9\u901a\u8fc7\u5408\u5e76\u5176\u5b50\u8282\u70b9\u7684\u7ed3\u679c\u6784\u9020\u800c\u6210\u3002treeIndex<\/span>\u00a0\u662f\u5f53\u524d\u6b63\u5728\u5904\u7406\u7684\u7ebf\u6bb5\u6811\u7684\u7d22\u5f15\u53f7\u3002
        \n\"\"
        \n\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u4e0a\u56fe\u4e2d\u7684\u6811\u53ef\u4ee5\u7531\u4e0b\u9762\u7684\u8f93\u5165\u6570\u636e\u6784\u9020\u51fa\uff1a\uff08\u672c\u6587\u901a\u7bc7\u90fd\u4f1a\u4f7f\u7528\u8fd9\u4e2a\u4f8b\u5b50\uff09<\/p>\n
        arr[] = { 18, 17, 13, 19, 15, 11, 20, 12, 33, 25 };<\/pre>\n
        \u4f60\u80fd\u731c\u5230\u672c\u4f8b\u4e2d\u7684merge<\/span>\u00a0\u64cd\u4f5c\u662f\u4ec0\u4e48\u5417\uff1f\u5728\u6784\u9020\u5b8c\u6bd5\u540e\uff0ctree[]<\/span>\u00a0\u6570\u7ec4\u770b\u8d77\u6765\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n
        tree[] = { 183, 82, 101, 48, 34, 43, 58, 35, 13, 19, 15, 31, 12, 33, 25, 18, 17, 0, 0, 0, 0, 0, 0, 11, 20, 0, 0, 0, 0, 0, 0 };<\/pre>\n
        \u6ce8\u610f\u5230tree[]<\/span>\u00a0\u6570\u7ec4\u672b\u5c3e\u7684\u90a3\u4e9b0\u4e86\u4e48\uff1f\u8fd9\u4e9b\u5c31\u662f\u6211\u4eec\u7528\u6765\u586b\u5145\u6811\uff0c\u4f7f\u4e4b\u6210\u4e3a\u5b8c\u5168\u6811\u7684null<\/span>\u00a0\u503c\uff08\u56e0\u4e3a\u6211\u4eec\u53ea\u670910\u4e2a\u53f6\u8282\u70b9\u3002\u5047\u82e5\u6211\u4eec\u670916\u4e2a\u53f6\u8282\u70b9\uff0c\u6211\u4eec\u5c31\u4e0d\u9700\u8981\u7528null<\/span>\u00a0\u586b\u5145\u4e86\u3002\u4f60\u80fd\u8bc1\u660e\u4e3a\u4ec0\u4e48\u5417\uff1f\uff09
        \n\u6ce8\u610f<\/strong>\uff1a\u5bf9\u4e8e\u4e0d\u540c\u7684\u95ee\u9898\uff0cmerge<\/span>\u00a0\u64cd\u4f5c\u662f\u4e0d\u540c\u7684\u3002\u5728\u6784\u9020\u7ebf\u6bb5\u6811\u4e4b\u524d\uff0c\u4f60\u9700\u8981\u4ed4\u7ec6\u8003\u8651\u5230\u5e95\u5728\u7ebf\u6bb5\u6811\u7684\u8282\u70b9\u4e2d\u9700\u8981\u5b58\u4ec0\u4e48\u6570\u636e\uff0c\u4ee5\u4fbf\u5728\u5408\u5e76\u7684\u65f6\u5019\u80fd\u591f\u7ed9\u51fa\u6700\u7ec8\u7684\u7ed3\u679c\u3002<\/p>\n
        2. \u8bfb\u53d6\/\u67e5\u8be2\u6570\u636e\u533a\u95f4\u6216\u7247\u6bb5<\/h4>\n
        int querySegTree(int treeIndex, int lo, int hi, int i, int j)\n{\n    \/\/ \u67e5\u8be2 arr[i..j]\n    if (lo > j || hi < i)               \/\/ \u7247\u6bb5\u5b8c\u5168\u8d85\u51fa\u8303\u56f4\n        return 0;                       \/\/ \u8868\u793a\u4e00\u4e2anull\u8282\u70b9\n    if (i <= lo && j >= hi)             \/\/ \u7247\u6bb5\u5b8c\u5168\u5728\u8303\u56f4\u5185\n        return tree[treeIndex];\n    int mid = lo + (hi - lo) \/ 2;       \/\/ \u5f53\u524d\u7247\u6bb5\u4e0e\u67e5\u8be2\u8303\u56f4\u6709\u90e8\u5206\u91cd\u5408\u3002\u9012\u5f52\u5230\u6df1\u4e00\u5c42\u3002\n    if (i > mid)\n        return querySegTree(2 * treeIndex + 2, mid + 1, hi, i, j);\n    else if (j <= mid)\n        return querySegTree(2 * treeIndex + 1, lo, mid, i, j);\n    int leftQuery = querySegTree(2 * treeIndex + 1, lo, mid, i, mid);\n    int rightQuery = querySegTree(2 * treeIndex + 2, mid + 1, hi, mid + 1, j);\n    \/\/ \u5408\u5e76\u67e5\u8be2\u7ed3\u679c\n    return merge(leftQuery, rightQuery);\n}\n\/\/ call this method as querySegTree(0, 0, n-1, i, j);\n\/\/ Here [i,j] is the range\/interval you are querying.\n\/\/ This method relies on \"null\" nodes being equivalent to storing zero.<\/pre>\n
        \u5728\u67e5\u8be2\u7684\u8303\u56f4\u5b8c\u5168\u5339\u914d\u5f53\u524d\u8282\u70b9\u7684\u8303\u56f4\u65f6\uff0c\u8be5\u65b9\u6cd5\u8fd4\u56de\u4e00\u4e2a\u7ed3\u679c\u3002\u5426\u5219\uff0c\u5b83\u5c06\u6df1\u5165\u6811\u7684\u4e0b\u4e00\u5c42\u6765\u5bfb\u627e\u6ee1\u8db3\uff08\u90e8\u5206\uff09\u67e5\u8be2\u8303\u56f4\u7684\u8282\u70b9\u3002<\/p>\n
        \u8fd9\u5c31\u662f\u7ebf\u6bb5\u6811\u7684\u7f8e\u4e3d\u6240\u5728<\/p><\/blockquote>\n
        \"\"
        \n\u5728\u4e0a\u8ff0\u4f8b\u5b50\u4e2d\uff0c\u6211\u4eec\u8bd5\u56fe\u627e\u5230[latex][2,8][\/latex]\u8303\u56f4\u5185\u7684\u8282\u70b9\u503c\u7684\u548c\u3002\u6ca1\u6709\u4e00\u4e2a\u533a\u95f4\u80fd\u76f4\u63a5\u6ee1\u8db3\u641c\u7d22\u8303\u56f4[latex][2,8][\/latex]\u3002\u7136\u800c\uff0c\u6211\u4eec\u53d1\u73b0\u8303\u56f4[latex][2,8][\/latex]\u53ef\u4ee5\u7531\u51e0\u4e2a\u5c0f\u8303\u56f4[latex][2,2], [3,4], [5,7], [8,8][\/latex]\u6765\u8868\u793a\u3002\u9a8c\u8bc1\u4e00\u4e0b\uff0c\u6211\u4eec\u53ef\u4ee5\u770b\u5230\u7d22\u5f15\u8303\u56f4\u5728[latex][2,8][\/latex]\u7684\u8282\u70b9\u503c\uff0c\u4ed6\u4eec\u7684\u548c\u662f[latex]13+19+15+11+20+12+33=123[\/latex]\u3002\u800c\u521a\u624d\u63d0\u5230\u7684\u90a3\u4e9b\u5c0f\u533a\u95f4[latex][2,2], [3,4], [5,7], [8,8][\/latex]\uff0c\u4ed6\u4eec\u6240\u5bf9\u5e94\u7684\u8282\u70b9\u7684\u548c\u662f[latex]13+34+43+33=123[\/latex].<\/p>\n
        3.\u66f4\u65b0\u5143\u7d20\u7684\u503c<\/h4>\n
        void updateValSegTree(int treeIndex, int lo, int hi, int arrIndex, int val)\n{\n    if (lo == hi) {                 \/\/ \u53f6\u5b50\u8282\u70b9\uff0c\u66f4\u65b0\u5143\u7d20\u503c.\n        tree[treeIndex] = val;\n        return;\n    }\n    int mid = lo + (hi - lo) \/ 2;   \/\/ \u5411\u66f4\u6df1\u5c42\u9012\u5f52\u4ee5\u67e5\u627e\u5bf9\u5e94\u8282\u70b9\n    if (arrIndex > mid)\n        updateValSegTree(2 * treeIndex + 2, mid + 1, hi, arrIndex, val);\n    else if (arrIndex <= mid)\n        updateValSegTree(2 * treeIndex + 1, lo, mid, arrIndex, val);\n    \/\/ \u5408\u5e76\u66f4\u65b0\u7ed3\u679c\n    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);\n}\n\/\/ call this method as updateValSegTree(0, 0, n-1, i, val);\n\/\/ Here you want to update the value at index i with value val.<\/pre>\n
        \u8fd9\u4e2a\u64cd\u4f5c\u7c7b\u4f3c\u4e8ebuildSegTree<\/span>\u00a0\u3002\u6211\u4eec\u6839\u636e\u66f4\u65b0\u8bf7\u6c42\u6765\u66f4\u65b0\u5bf9\u5e94\u7684\u53f6\u5b50\u8282\u70b9\u3002\u968f\u540e\u8fd9\u4e9b\u53d8\u66f4\u5411\u4e0a\u4f20\u9012\u5230\u5176\u7236\u8282\u70b9\u3002
        \n\"\"
        \n\u5728\u8fd9\u4e2a\u4f8b\u5b50\u4e2d\uff0c\u4f4d\u4e8e(\u8f93\u5165\u6570\u636e\u4e2d)\u7d22\u5f151,3\u548c6\u7684\u5143\u7d20\uff0c\u4ed6\u4eec\u7684\u503c\u5bf9\u5e94\u589e\u52a0\u4e86+3, -1\u4e0e+2\u3002\u4ece\u56fe\u4e2d\u53ef\u4ee5\u770b\u51fa\u8fd9\u4e9b\u503c\u662f\u5982\u4f55\u5411\u4e0a\u4f20\u9012\u66f4\u65b0\uff0c\u76f4\u81f3\u6839\u8282\u70b9\u7684\u3002<\/p>\n
        \u590d\u6742\u5ea6\u5206\u6790<\/h3>\n
        \u6211\u4eec\u6765\u770b\u4e00\u4e0bbuild<\/span>\u00a0\u8fc7\u7a0b\u3002\u6211\u4eec\u4f1a\u8bbf\u95ee\u7ebf\u6bb5\u6811\u7684\u6bcf\u4e2a\u53f6\u8282\u70b9\uff08\u5bf9\u5e94\u5230\u8f93\u5165\u6570\u7ec4arr[]<\/span>\u00a0\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\uff09\u3002\u8fd9\u5c31\u5f62\u6210\u4e86[latex]n[\/latex]\u4e2a\u53f6\u8282\u70b9\u3002\u6b64\u5916\u6211\u4eec\u8fd8\u6709[latex]n-1[\/latex]\u4e2a\u975e\u53f6\u8282\u70b9\u3002\u56e0\u6b64\u603b\u5171\u4f1a\u6709\u7ea6[latex]2*n[\/latex]\u4e2a\u8282\u70b9\u3002\u8fd9\u6837\u8bf4\u6765\u6574\u4e2a\u6784\u9020\u6811\u7684\u8fc7\u7a0b\u7684\u4f1a\u5728[latex]O(n)[\/latex]\u5373\u7ebf\u6027\u65f6\u95f4\u5185\u5b8c\u6210\u3002
        \nupdate<\/span>\u00a0\u8fc7\u7a0b\u5728\u8fbe\u5230\u76ee\u6807\u53f6\u8282\u70b9\u7684\u8fc7\u7a0b\u4e2d\uff0c\u5728\u9012\u5f52\u7684\u6bcf\u4e00\u5c42\u90fd\u4f1a\u4e22\u5f03\u4e00\u534a\u7684\u8303\u56f4\u3002\u8fd9\u4e2a\u8fc7\u7a0b\u7c7b\u4f3c\u4e8e\u4e8c\u5206\u641c\u7d22\uff0c\u9700\u8981\u5bf9\u6570\u7ea7\u7684\u65f6\u95f4\u3002\u5728\u53f6\u8282\u70b9\u66f4\u65b0\u8fc7\u540e\uff0c\u5b83\u7684\u6bcf\u4e00\u4e2a\u76f4\u7cfb\u7236\u8282\u70b9\u4e5f\u90fd\u5c06\u88ab\u66f4\u65b0\uff0c\u8fd9\u4e2a\u8fc7\u7a0b\u8017\u8d39\u7684\u65f6\u95f4\u662f\u6811\u7684\u9ad8\u5ea6\u7684\u7ebf\u6027\u7ea7\u522b\u3002
        \nread\/query<\/span>\u00a0\u8fc7\u7a0b\u6309\u7167\u6df1\u5ea6\u4f18\u5148\u904d\u5386\u6811\uff0c\u5bfb\u627e\u7b26\u5408\u641c\u7d22\u6761\u4ef6\u7684\u8282\u70b9\u8303\u56f4\u3002\u5728\u6700\u4f18\u60c5\u51b5\u4e0b\uff0c\u6211\u4eec\u7684\u8303\u56f4\u5927\u4e8e\u6216\u7b49\u4e8e\u6839\u8282\u70b9\u7684\u8303\u56f4\uff0c\u6b64\u65f6\u76f4\u63a5\u80fd\u4ece\u6839\u8282\u70b9\u5f97\u5230\u7ed3\u679c\u3002\u6700\u5dee\u60c5\u51b5\u4e0b\uff0c\u6211\u4eec\u641c\u7d22\u4e00\u4e2a\u957f\u5ea6\u4e3a1\u7684\u8303\u56f4\uff08\u5bf9\u5e94\u4e8e\u7ebf\u6bb5\u6811\u4e2d\u7684\u4e00\u4e2a\u53f6\u8282\u70b9\uff09\uff0c\u6b64\u65f6\u6211\u4eec\u8bbf\u95ee\u7684\u8282\u70b9\u4e2a\u6570\u7b49\u4e8e\u6811\u7684\u9ad8\u5ea6\uff1b\u5373\u641c\u7d22\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u6811\u7684\u9ad8\u5ea6\u7ebf\u6027\u76f8\u5173\u3002
        \n\"\"
        \n\u8fd9\u5c31\u662f\u4e4b\u524d\u8bf4\u8fc7\u7684\uff1a<\/p>\n
        \u4e00\u4e2a\u542b\u6709[latex]n[\/latex]\u4e2a\u5143\u7d20\u8303\u56f4\u7684\u7ebf\u6bb5\u6811\u53ef\u4ee5\u7528\u4e00\u4e2a\u5927\u5c0f\u7ea6\u4e3a[latex]4*n[\/latex]\u7684\u6570\u7ec4\u8868\u793a<\/p><\/blockquote>\n
        \u8fd9\u4fdd\u8bc1\u4e86\u6211\u4eec\u6211\u4eec\u751f\u6210\u7684\u7ebf\u6bb5\u6811\u662f\u4e00\u4e2a\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u8fdb\u4e00\u6b65\u53c8\u4fdd\u8bc1\u4e86\u8fd9\u68f5\u6811\u9ad8\u5ea6\u7684\u4e0a\u754c\u662f\u8f93\u5165\u89c4\u6a21\u7684\u5bf9\u6570\u7ea7\u3002
        \nViola! \u4e0d\u8bba\u662fread<\/span>\u00a0\u8fd8\u662fupdate<\/span>\u00a0\u7684\u67e5\u8be2\u90fd\u53ea\u9700\u8981\u5bf9\u6570\u7ea7\u7684[latex]O(log_2(n))[\/latex]\u65f6\u95f4\uff0c\u8fd9\u6b63\u662f\u6211\u4eec\u60f3\u8981\u7684\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
        \u672c\u6587\u7ffb\u8bd1\u81eahttps:\/\/leetcode.com\/articles\/recursive-approach-segment-trees-range-sum-queries-lazy-propagation\/\uff0c\u5982\u6709\u4fb5\u6743\u8bf7\u76f4\u63a5Email\u6211 \u7b80\u4ecb \u4ec0\u4e48\u662f\u7ebf\u6bb5\u6811(Segment Tree) \u7ebf\u6bb5\u6811\u662f\u4e00\u79cd\u4e8c\u53c9\u6811\uff0c\u6811\u4e2d\u7684\u6bcf\u4e00\u4e2a\u8282\u70b9\u4ee3\u8868\u4e00\u6bb5\u533a\u95f4\u3002\u901a\u5e38\u4e00\u4e2a\u8282\u70b9\u50a8\u5b58\u8fd9\u4e2a\u533a\u95f4\u7684\u4e00\u4e2a\u6216\u591a\u4e2a\u5c5e\u6027\u7528\u4e8e\u540e\u7eed\u67e5\u8be2\u3002 \u4e3a\u4ec0\u4e48\u8981\u4f7f\u7528\u7ebf\u6bb5\u6811\uff08\u5b83\u7684\u7279\u70b9\u662f\u4ec0\u4e48\uff09? \u8bb8\u591a\u95ee\u9898\u9700\u8981\u6211\u4eec\u7ed9\u51fa\u6570\u636e\u96c6\u5728\u67d0\u4e2a\u533a\u95f4\u6216\u8005\u7247\u6bb5\u5185\u7684\u67e5\u8be2\u7ed3\u679c\u3002\u7279\u522b\u662f\u5f53\u51fa\u73b0\u5927\u91cf\u3001\u91cd\u590d\u7684\u67e5\u8be2\u65f6\uff0c\u8fd9\u7c7b\u64cd\u4f5c\u4f1a\u53d8\u5f97\u5197\u957f\u6216\u7f13\u6162\u3002\u4e00\u4e2a\u7ebf\u6bb5\u6811\u53ef\u4ee5\u8ba9\u6211\u4eec\u5728\u5bf9\u6570\u7ea7\u65f6\u95f4\u590d\u6742\u5ea6\u5185\u5f97\u5230\u8fd9\u7c7b\u95ee\u9898\u7684\u67e5\u8be2\u7ed3\u679c\u3002 \u7ebf\u6bb5\u6811\u5728\u8ba1\u7b97\u96c6\u5408\u5b66\u3001GIS\u7b49\u9886\u57df\u6709\u76f8\u5173\u5e94\u7528\u3002\u4f8b\u5982\uff0c\u6211\u4eec\u53ef\u80fd\u4f1a\u5728\u8ddd\u79bb\u67d0\u4e2a\u4e2d\u5fc3\u70b9\/\u539f\u70b9\u9644\u8fd1\u4e00\u6bb5\u8ddd\u79bb\u7684\u7a7a\u95f4\u8303\u56f4\u5185\u6709\u5927\u91cf\u7684\u53c2\u8003\u70b9\u3002\u5047\u8bbe\u6211\u4eec\u9700\u8981\u67e5\u8be2\u8ddd\u79bb\u539f\u70b9\u6307\u5b9a\u8ddd\u79bb\u8303\u56f4\u5185\u7684\u76f8\u5173\u53c2\u8003\u70b9\u3002\u4e00\u4e2a\u666e\u901a\u7684\u67e5\u8be2\u8868\u9700\u8981\u7ebf\u6027\u9636\u7684\u65f6\u95f4\u6765\u626b\u63cf\u6240\u6709\u7684\u70b9\u6216\u6240\u6709\u53ef\u80fd\u7684\u8ddd\u79bb\uff08\u60f3\u4e00\u4e0bhash map\uff09\u3002\u7ebf\u6bb5\u6811\u5141\u8bb8\u6211\u4eec\u5728\u5bf9\u6570\u65f6\u95f4\u5185\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\uff0c\u5e76\u4e14\u62e5\u6709\u66f4\u5c11\u7684\u7a7a\u95f4\u6d88\u8017\u3002\u8fd9\u7c7b\u95ee\u9898\u88ab\u79f0\u4f5c Planar Range Searching\u3002\u9ad8\u6548\u89e3\u51b3\u8fd9\u7c7b\u95ee\u9898\u662f\u81f3\u5173\u91cd\u8981\u7684\uff0c\u7279\u522b\u662f\u5728\u5904\u7406\u90a3\u4e9b\u5feb\u901f\u53d8\u6362\u3001\u65e0\u6cd5\u9884\u77e5\u7684\u52a8\u6001\u6570\u636e\u65f6\uff08\u4f8b\u5982\uff0c\u4e00\u4e2a\u7a7a\u7ba1\u96f7\u8fbe\u7cfb\u7edf\uff09\u3002 \u672c\u6587\u7a0d\u540e\u4f1a\u89e3\u51b3\u533a\u95f4\u548c\u67e5\u8be2\u95ee\u9898\uff08Range Sum Query Problem\uff09\u4f5c\u4e3a\u4e00\u4e2a\u4f8b\u5b50\uff0c\u501f\u6b64\u8bf4\u660e\u7ebf\u6bb5\u6811\u662f\u5982\u4f55\u8282\u7701\u7a7a\u95f4\u53ca\u5b9e\u65f6\u4ee3\u4ef7\u3002 \u6211\u4eec\u5c06\u4f1a\u4f7f\u7528\u4e0a\u56fe\u4f5c\u4e3a\u4e00\u4e2a\u5b9e\u4f8b\u6765\u4ecb\u7ecd\u7528\u4e8e\u201c\u533a\u95f4\u548c\u67e5\u8be2\u201d\u7684\u7ebf\u6bb5\u6811\u5b83\u957f\u4ec0\u4e48\u6837\uff0c\u4ee5\u53ca\u6709\u4f55\u7279\u6027\u3002 \u5982\u4f55\u751f\u6210\u4e00\u4e2a\u7ebf\u6bb5\u6811 \u6211\u4eec\u5c06\u6570\u636e\u4fdd\u5b58\u5728\u5927\u5c0f\u4e3a[latex]n[\/latex]\u7684\u6570\u7ec4arr[]\u00a0\u4e2d\u3002 \u7ebf\u6bb5\u6811\u6811\u7684\u6839\u901a\u5e38\u8868\u793a\u6574\u4e2a\u6570\u636e\u7684\u533a\u95f4\u8303\u56f4\uff0c\u5373arr[0:n-1]\u00a0\uff1b \u6811\u7684\u6bcf\u4e00\u4e2a\u53f6\u8282\u70b9\u8868\u793a\u5355\u4e2a\u5143\u7d20\uff08\u6216\u53ea\u6709\u4e00\u4e2a\u5143\u7d20\u7684\u533a\u95f4\uff09\u3002\u56e0\u6b64\u53f6\u8282\u70b9\u8868\u793a\u7684\u6570\u503c\u4e3aarr[0]\u00a0,arr[1]\u00a0\u76f4\u81f3arr[n-1]\u00a0\uff1b \u6811\u7684\u975e\u53f6\u8282\u70b9\u8868\u793a\u5176\u5b50\u8282\u70b9\u5408\u5e76(merge\/union)\u540e\u7684\u7ed3\u679c\uff1b \u6bcf\u4e00\u4e2a\u5b50\u8282\u70b9\u90fd\u80fd\u8868\u793a\u5176\u7236\u8282\u70b9\u4e00\u534a\u7684\u533a\u95f4\u8303\u56f4\uff1b \u4e00\u4e2a\u5305\u542b[latex]n[\/latex]\u4e2a\u5143\u7d20\u8303\u56f4\u7684\u7ebf\u6bb5\u6811\u53ef\u4ee5\u7528\u4e00\u4e2a[latex]\\approx 4 * n[\/latex]\u5927\u5c0f\u7684\u6570\u7ec4\u8868\u793a\u3002\uff08\u5176\u539f\u56e0\u5728StackOverflow\u4e0a\u6709\u8be6\u5c3d\u7684\u8ba8\u8bba\u3002\u5982\u679c\u4f60\u4ecd\u4e0d\u76f8\u4fe1\uff0c\u6ca1\u5173\u7cfb\uff0c\u6211\u4eec\u7a0d\u540e\u4f1a\u8fdb\u4e00\u6b65\u8ba8\u8bba\u3002\uff09 \u600e\u4e48\uff08\u7528\u6570\u7ec4\uff09\u5b58\u5462\uff1f \u601d\u8def\u5f88\u7b80\u5355\uff1a\u4e00\u4e2a\u7d22\u5f15\u53f7\u4e3a[latex]i[\/latex]\u7684\u8282\u70b9\uff0c\u4ed6\u7684\u5b50\u8282\u70b9\u7684\u7d22\u5f15\u53f7\u4e3a[latex](2*i+1)[\/latex]\u4ee5\u53ca[latex](2*i+2)[\/latex]. \u5728\u4f7f\u7528\u9012\u5f52\u65b9\u6cd5\u6784\u5efa\u65f6\uff0c\u7ebf\u6bb5\u6811\u975e\u5e38\u76f4\u89c2\u4e14\u5bb9\u6613\u4f7f\u7528\u3002 \u7ebf\u6bb5\u6811\u7684\u9012\u5f52\u65b9\u6cd5 \u6211\u4eec\u5c06\u4f7f\u7528\u6570\u7ec4tree[]\u00a0\u6765\u4fdd\u5b58\u7ebf\u6bb5\u6811\uff08\u75280\u503c\u521d\u59cb\u5316\uff09\u7684\u8282\u70b9\u5c5e\u6027\u3002\u4ee5\u4e0b\u662f\u5177\u4f53\u7684\u5b58\u50a8\u65b9\u6848\uff08\u4f7f\u7528\u4ee50\u5f00\u59cb\u7684\u7d22\u5f15\u53f7\uff09\uff1a \u6811\u7684\u6839\u8282\u70b9\u7d22\u5f15\u4e3a0\uff0c\u5373tree[0] \u8282\u70b9tree[i]\u00a0\u7684\u5b50\u8282\u70b9\u5b58\u50a8\u5728tree[2*i+1]\u00a0\u53catree[2*i+2]\u00a0\u4e2d \u5f53\u6570\u7ec4\u5143\u7d20\u6570\u91cf\u4e0d\u662f2\u7684k\u6b21\u65b9\uff08\u59822,4,8,16,32…\uff09\u65f6\uff0c\u7528\u00a00\u00a0\u00a0\u6216null\u00a0\u586b\u5145\u4e0d\u8db3\u7684\u5143\u7d20\u503c \u6211\u4eec\u771f\u7684\u9700\u8981\u75280\u586b\u5145\u4e48? \u4e0d\u5b8c\u5168\u662f\u3002\u53ea\u662f\u9700\u8981\u4fdd\u8bc1tree[]\u8db3\u591f\u5927\uff0c\u5e76\u4e14\u521d\u59cb\u503c\u90fd\u662f0\uff0c\u800c\u4e14\u4e0d\u9700\u8981\u62c5\u5fc3\u989d\u5916\u7684\u53f6\u8282\u70b9\u6ca1\u6709\u88ab\u5904\u7406\u8fc7\u3002 \u53f6\u8282\u70b9\u7684\u7d22\u5f15\u8303\u56f4\u662f[latex]2^k-1[\/latex]\u5230[latex]2^(k+1)-2[\/latex] \u6211\u4eec\u53ea\u9700\u8981\u4e0b\u5217\u4e09\u4e2a\u65b9\u6cd5\uff1a 1.\u6839\u636e\u7ed9\u5b9a\u6570\u636e\u6784\u9020\u7ebf\u6bb5\u6811 void buildSegTree(vector<int>& arr, int treeIndex, int lo, int hi) { if (lo == hi) { […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[164],"class_list":["post-2195","post","type-post","status-publish","format-standard","hentry","category-study","tag-164"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2195","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2195"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2195\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2195"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2195"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2195"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}