Concise solution in O(sqrt N)

  • 1

    idea is to divide the array into sqrt N blocks of sums.

    #include <cmath>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long ll;
    class NumArray {
        vector<int> a;
        vector<ll> segs;
        size_t numseg;
        NumArray(vector<int> &nums) : a(nums) {
            size_t len = nums.size();
            numseg = (size_t)ceil(sqrt(len));
            size_t i=0;
            for (i=0;i < len; i+=numseg){
                ll sum=0;
                for (size_t j = i; j < min(len,i+numseg); j++){
        void update(int i, int val) {
            segs[i/numseg] += val-a[i];
            a[i] = val;
        int sumRange(int i, int j) {
            size_t s1 = i/numseg;
            size_t s2 = j/numseg;
            ll sum=0;
            // sum the blocks
            for (size_t k=s1; k <=s2;k++)
                sum += segs[k];
            // minus off excess
            for (int k=s1*numseg; k<i;k++)
                sum -= a[k];
            for (int k=j+1; k < min(a.size(),(s2+1)*numseg); k++)
                sum -= a[k];
            return sum;

Log in to reply

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