区间单值修改

本文主要是介绍区间单值修改，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即，nums[left] + nums[left + 1], ..., nums[right]）

• 树状数组
• 线段树

树状数组

class NumArray {

    private int[] nums;

    private TreeArray treeArray;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.treeArray = new TreeArray(nums);
    }

    public void update(int index, int val) {
        if (nums[index] != val) {
            treeArray.add(index + 1, val - nums[index]);
        }
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        return treeArray.regionSum(left, right + 1);
    }
}

class TreeArray {
    private int size;
    private int[] data;

    public TreeArray(int[] nums) {
        this.size = nums.length;
        this.data = new int[size + 1];

        for (int i = 0; i < nums.length; ++i) {
            add(i + 1, nums[i]);
        }
    }

    private int lowbit(int x) {
        return x & (-x);
    }

    public void add(int index, int val) {
        while (index <= size) {
            data[index] += val;
            index += lowbit(index);
        }
    }

    private int query(int index) {
        int ret = 0;
        while (index > 0) {
            ret += data[index];
            index -= lowbit(index);
        }
        return ret;
    }

    public int regionSum(int left, int right) {
        return query(right) - query(left);
    }
}

线段树

class NumArray {

    private int[] nums;

    private SegmentTree segmentTree;

    public NumArray(int[] nums) {
        this.nums = nums;
        segmentTree = new SegmentTree(nums);
    }

    public void update(int index, int val) {
        segmentTree.update(index + 1, index + 1, val, 1, nums.length, 1);
    }

    public int sumRange(int left, int right) {
        return segmentTree.query(left + 1, right + 1, 1, nums.length, 1);
    }
}

class SegmentTree {
    private int n;
    private int[] data;
    private int[] sum;
    private boolean[] update;
    private int[] change;

    public SegmentTree(int[] nums) {
        this.n = nums.length;
        this.data = nums;
        this.sum = new int[n << 2 | 1];
        this.update = new boolean[n << 2 | 1];
        this.change = new int[n << 2 | 1];
        build(1, n, 1);
    }
    
    public void build(int l, int r, int rt) {
        if (l == r) {
            sum[rt] = data[l - 1];
            System.out.println(rt + " " + (l - 1));
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 ^ 1);
        pushUp(rt);
    }

    private void pushUp(int rt) {
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }

    private void pushDown(int rt, int ln, int rn) {
        if (update[rt]) {
            change[rt << 1] = change[rt];
            change[rt << 1 | 1] = change[rt];
            update[rt << 1] = true;
            update[rt << 1 | 1] = true;
            sum[rt << 1] = change[rt] * ln;
            sum[rt << 1 | 1] = change[rt] * rn;
            update[rt] = false;
        }
    }

    public void update(int L, int R, int V, int l, int r, int rt) {
        if (L <= l && r <= R) {
            update[rt] = true;
            change[rt] = V;
            sum[rt] = (r - l + 1) * V;
            return;
        }
        int mid = (l + r) >> 1;

        pushDown(rt, mid - l + 1, r - mid);

        if (L <= mid) {
            update(L, R, V, l, mid, rt << 1);
        }

        if (mid < R) {
            update(L, R, V, mid + 1, r, rt << 1 | 1);
        }

        pushUp(rt);
    }

    public int query(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) {
            return sum[rt];
        }

        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);

        int ret = 0;

        if (L <= mid) {
            ret += query(L, R, l, mid, rt << 1);
        }

        if (mid < R) {
            ret += query(L, R, mid + 1, r, rt << 1 | 1);
        }

        return ret;
    }
}

这篇关于区间单值修改的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！