C++ very simple - just buffering updates - 1750 ms - no special trees just vectors
The update is O(N) but with a good constant factor since it's 0(N) every 333 times and O(1) the rest;\nSumRange is 0(1).\n\n    class NumArray {\n    public:\n 
The update is O(N) but with a good constant factor since it's 0(N) every 333 times and O(1) the rest;\nSumRange is 0(1).\n\n    class NumArray {\n    public:\n        NumArray(vector<int> &nums) : psum( nums.size()+1, 0 ), nums(nums)\n        {\n            partial_sum( nums.begin(), nums.end(), psum.begin() + 1);\n        }\n    \n        void update(int i, int val) \n        {\n            updates.emplace_back( i,  val - nums[i]);\n            nums[i] = val;        \n            \n            if ( updates.size() > 333) //magic\n            {\n                partial_sum( nums.begin(), nums.end(), psum.begin() + 1);\n                updates.clear();\n            }\n        }\n    \n        int sumRange(int i, int j)\n        {\n            auto result =  psum[j+1] - psum[i];\n            \n            for (const auto& p : updates)\n            {\n                if ( p.first <=j && p.first >= i)\n                {\n                    result += p.second;\n                }\n            }\n            \n            return result;\n        }\n        \n    private:    \n        vector<int64_t> psum;\n        vector<int> nums;\n        vector<pair<int,int>> updates;\n    };
[]