SQRT分解

• 是一種數(shù)據(jù)結(jié)構(gòu)
• 使用分塊(分組)的思想
• 解決區(qū)間問題
• 動態(tài)維護

分區(qū)

基本思想

更新

代碼示例

leetcode 307 可變數(shù)組
給你一個數(shù)組 nums ，請你完成兩類查詢，其中一類查詢要求更新數(shù)組下標對應(yīng)的值，另一類查詢要求返回數(shù)組中某個范圍內(nèi)元素的總和。
實現(xiàn) NumArray 類：
NumArray(int[] nums) 用整數(shù)數(shù)組 nums 初始化對象
void update(int index, int val) 將 nums[index] 的值更新為 val
int sumRange(int left, int right) 返回子數(shù)組 nums[left, right] 的總和（即，nums[left] + nums[left + 1], ..., nums[right]）

class NumArrayMuSqrt {

    private int[] data, blocks;//block 表示每組的數(shù)據(jù)
    private int N; //元素總數(shù)
    private int B; //每組元素個數(shù)
    private int Bn; //組數(shù)

    public NumArrayMuSqrt(int[] nums) {

        N = nums.length;
        if (N == 0)
            return;
        B = (int) Math.sqrt(N);
        //是否能整除
        Bn = N / B + (N % B > 0 ? 1 : 0);

        data = Arrays.copyOf(nums, N);

        blocks = new int[Bn];
        for (int i = 0; i < N; i++)
            blocks[i / B] += nums[i];
    }

    public void update(int index, int val) {
        if(index < 0 || index >= N)
            return;
        int b = index / B;

        blocks[b] -= data[index];
        blocks[b] += val;

        data[index] = val;
    }

    public int sumRange(int x, int y) {

        if (x < 0 || x >= N || y < 0 || y >= N || x > y)
            return 0;

        int bstart = x / B;
        int bend = y / B;

        int res = 0;
        if (bstart == bend){
            for (int i = x; i <= y; i++)
                res += data[i];
            return res;
        }

        //(bstart + 1)*B  bstart組的下一組的第一個節(jié)點  從bstart 遍歷到這一組的最后一個元素
        for (int i = x; i < (bstart + 1) * B; i++)
            res += data[i];

        for (int b = bstart + 1; b < bend; b++)
            res += blocks[b];

        for (int i = bend * B; i <= y; i++) {
            res += data[i];
        }
        return res;
    }
}