56 ms C++ segment tree solution


  • 0
    Y

    For segment tree, see https://en.wikipedia.org/wiki/Segment_tree. And useful link https://en.wikipedia.org/wiki/Range_minimum_query

     class NumArray {
            vector<int> nums;
            vector<int> memo;
            int buildSegmentTree(int idx, int l, int h) {
                if (l == h) {
                    memo[idx] = nums[l];
                    return memo[idx];
                }
                int m = l + (h - l) / 2;
                int left = buildSegmentTree(2 * idx + 1, l, m);
                int right = buildSegmentTree(2 * idx + 2, m + 1, h);
                memo[idx] = left + right;
                return memo[idx];
            }
            int query(int i, int j, int l, int h, int idx) {
                if (i > h || j < l) {
                    return 0;
                }
                if (i <= l && j >= h) {
                    return memo[idx];
                }
                int m = l + (h - l) / 2;
                int left = query(i, j, l, m, 2 * idx + 1);
                int right = query(i, j, m + 1, h, 2 * idx + 2);
                return left + right;
            }
            void updateInternal(int i, int l, int h, int idx, int diff) {
                if (i < l || i > h) {
                    return;
                }
                if (l == h) {
                    if (i == l) memo[idx] += diff;
                    return;
                }
                if (i >= l && i <= h) {
                    memo[idx] += diff;
                }
                int m = l + (h - l) / 2;
                updateInternal(i, l, m, idx * 2 + 1, diff);
                updateInternal(i, m + 1, h, idx * 2 + 2, diff);
            }
        public:
            NumArray(vector<int> &nums) {
                this->nums = nums;
                int n = nums.size();
                if (n > 0) {
                    int lgn = ceil(log2(n)) + 1;
                    memo.resize(1 << lgn, 0);
                    buildSegmentTree(0, 0, n - 1);
                }
            }
        
            void update(int i, int val) {
                int diff = val - nums[i];
                nums[i] = val;
                updateInternal(i, 0, nums.size() - 1, 0, diff);
            }
        
            int sumRange(int i, int j) {
                return query(i, j, 0, nums.size() - 1, 0);
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.