C++ solution using "buckets". O(1) for updating and O(n^0.5) for query in the worst case (not the fast).
The idea is using \u201cbuckets\u201d.  Assume the length of the input array is n, we can partition the whole array into m buckets, with each bucket having k=n/
The idea is using \u201cbuckets\u201d.  Assume the length of the input array is n, we can partition the whole array into m buckets, with each bucket having k=n/m elements. For each bucket, we record two kind of information: 1) a copy of elements in the bucket, 2) the sum of all the elements in the bucket.\n\nFor example: If the input is [0,1,2,3,4,5,6,7,8,9], and we partition it into 4 buckets, formatted as {[numbers], sum}: \n\n - bucket0: {[0, 1, 2], 3}\n - bucket1: {[3, 4, 5], 12}\n - bucket2: {[6, 7, 8], 21} \n - bucket3: {[9], 9};\n\nUpdating is easy. You just need to find the right bucket, modify the element value, and change the \u201csum\u201d value in that bucket accordingly. The operation takes O(1) time.\n\nSummation is a little complicated. In the above example, let\u2019s say we want to compute the sum in range [1, 7]. We can see, the numbers we want to accumulate are in bucket0, bucket1, and bucket2. Specifically, we only need parts of numbers in bucket0 and bucket2, and all the numbers in bucket1. Because the summation of all numbers in bucket1 have already been computed, we don\u2019t need to compute it again. So, instead of doing (1+2) + (3+4+5) + (6+7), we can just do (1+2) + 12 + (6+7).  We save two \u201c+\u201d operations. If you change the size of buckets, the number of saved \u201c+\u201d operations will be different. The questions is:\n\n**What is the best size that can save the most \u201c+\u201d operations?**\n\nHere is my analysis, which might be incorrect.\n\nWe have:\n\n - The number of buckets is **m**. \n - The size of each bucket is **k**. \n - The length of input array is **n**, and we have **mk=n**.\n\nIn the worst case (the query is [0, n-1]), we will first add all the elements in bucket0, then add from bucket1 to bucket(m-2), and finally add all the elements in bucket(m-1), so we do **2k+m-2** \u201c+\u201d operations. We want to find the minimum value of **2k+m**. Because **2km=2n**, when **2k=m**, **2k+m** reaches the minimum value. (Need proof?) So we have **m = sqrt(2n)** and **k=sqrt(n/2)**. \n\nTherefore, in the worst case, the best size of bucket is **k=sqrt(n/2)**, and the complexity is **O(2k+m-2)=O(2m-2)=O(m)=O(sqrt(2n))=O(n^0.5)**;\n\nThank you for pointing out any mistake!\n\n    class NumArray {\n    public:\n        \n        struct Bucket\n        {\n            int sum;\n            vector<int> val;\n        };\n        \n        int bucketNum;\n        int bucketSize;\n        vector<Bucket> Bs;\n    \n        NumArray(vector<int> &nums) {\n            int size = nums.size();\n            int bucketNum = (int)sqrt(2*size);\n            bucketSize = bucketNum/2;\n            while(bucketSize * bucketNum<size) ++bucketSize;\n            \n            Bs.resize(bucketNum);\n            for(int i=0, k=0; i<bucketNum; ++i)\n            {\n                int temp = 0;\n                Bs[i].val.resize(bucketSize);\n                for(int j=0; j<bucketSize && k<size; ++j, ++k)\n                {\n                    temp += nums[k];\n                    Bs[i].val[j] = nums[k];\n                }\n                Bs[i].sum = temp;\n            }\n        }\n    \n        void update(int i, int val) {\n            int x = i / bucketSize;\n            int y = i % bucketSize;\n            Bs[x].sum += (val - Bs[x].val[y]);\n            Bs[x].val[y] = val;\n        }\n    \n        int sumRange(int i, int j) {\n            int x1 = i / bucketSize;\n            int y1 = i % bucketSize;\n    \t\tint x2 = j / bucketSize;\n            int y2 = j % bucketSize;\n            int sum = 0;\n    \n    \t\tif(x1==x2)\n    \t\t{\n    \t\t\tfor(int a=y1; a<=y2; ++a)\n    \t\t\t{\n    \t\t\t\tsum += Bs[x1].val[a];\n    \t\t\t}\n    \t\t\treturn sum;\n    \t\t}\n    \n    \t\tfor(int a=y1; a<bucketSize; ++a)\n    \t\t{\n    \t\t\tsum += Bs[x1].val[a];\n    \t\t}\n            for(int a=x1+1; a<x2; ++a)\n            {\n                sum += Bs[a].sum;\n            }\n            for(int b=0; b<=y2; ++b)\n            {\n                sum += Bs[x2].val[b];\n            }\n            return sum;\n        }\n    };
['C++']