Mutant House Robber
This is a house robber on a mutating array.\n\nTo speed things up, we split the street into smaller parts. We can then update the affected part only, and combin
This is a house robber on a mutating array.\n\nTo speed things up, we split the street into smaller parts. We can then update the affected part only, and combine the result.\n\n#### SQRT Segmentation\n\nThe time complexity for this solution is O(m sqrt n). The second solution uses a logarithmic data structure bring it down to O(m log n).\n\nI think that the SQRT Segmentation solution is a bit easier to understand, so I recommend to start with it.\n\nWe split the streen into `sqrt(len(num))` parts. When we process a query, we update the value and re-run `rob` only for the affected part. \n\nThen, we `glue` all parts to get the final result. In order to `glue` parts, we need to track `4` best results:\n1.  `[*][*]...[*][*]`: From first to last (`_11`)\n2.  `[*][*]...[*][ ]`: From first to second last (`_10`)\n3.  `[ ][*]...[*][*]`: Second to last (`_01`)\n4.  `[ ][*]...[*][ ]`: Second to second last (`_00`)\n\nWhen gluing two parts, we can combine previous second lasts with firsts, or previous lasts with seconds.\n\n> Note: variable names are just for fun.\n> Note: the Python solution started SLE as of 05/27.\n<iframe src="https://leetcode.com/playground/KQMzXbZc/shared" frameBorder="0" width="700" height="450"></iframe>\n\n#### Segment Tree\nNow, we can do the same as above but for logarithmic intervals. Having defined the `glue` function, we can otherwise use the standard segment tree implementation.\n\nFor this problem and test cases, the segment tree solution is actually 200 ms slower than SQRT Segmentation.\n\nThis is, perhaps, because of memory overhead of the segment tree. It will become faster if we increase the size of the input array. \n\n<iframe src="https://leetcode.com/playground/Tko3YFaR/shared" frameBorder="0" width="700" height="500"></iframe>\n\n#### Black Magic (now TLE)\nJust found this solution. I am still figuring out how exactly this works, but it the simplest and fastest solution by far.\n\nFor the test cases in this solution, it looks like it process no more than 12 elements in `dp` during an update.\n\n> Update: this solution is TLE now, so it worked fast for weaker test cases.\n\n**C++**\n```cpp\nlong long dp[50001] = { 0 }; // Only need to initialize the first element.\nclass Solution {\npublic:\nint maximumSumSubsequence(vector<int>& n, vector<vector<int>>& queries) {\n    for (int i = 0; i < n.size(); ++i)\n        dp[i + 1] = max(n[i] - dp[i], 0LL);\n    long long sum = accumulate(begin(dp), begin(dp) + n.size() + 1, 0), res = 0;\n    for (const auto &q : queries) {\n        n[q[0]] = q[1];\n        for (int i = q[0]; i < n.size(); ++i) {\n            int temp = max(n[i] - dp[i], 0LL);\n            if (temp == dp[i + 1])\n                break;\n            sum += temp - dp[i + 1];\n            dp[i + 1] = temp;\n        }\n        res += sum;\n    }\n    return res % 1000000007;\n}\n};\n```
['C']