Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9

update(1, 2)

sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly
public class NumArray {

    private SegmentTreeNode root = null;

    private int size = 0;

    public NumArray(int[] nums) {

        root = buildInSegmentTree(nums, 0, nums.length - 1);

        size = nums.length;

    }

    void update(int i, int val) {

        if(i<0 || i>=size) return;

        updateInSegmentTree(root, i, val);

    }

    public int sumRange(int i, int j) {

        if(i>j || i<0 || j>=size)  return -1;

        return querySum(root, i, j);

    }

    class SegmentTreeNode{

        int lc = 0, rc = 0, sum = 0;

        SegmentTreeNode left = null, right = null;

        SegmentTreeNode(int l, int r, int val) {

            lc = l; rc = r; sum = val;

        }

    }

    public SegmentTreeNode buildInSegmentTree(int []nums, int l, int r) {

        if(l > r) return null;

        if(l == r) {

            SegmentTreeNode leaf = new SegmentTreeNode(l, r, nums[l]);

            return leaf;

        }

        SegmentTreeNode root = new SegmentTreeNode(l, r, 0);

        int mid = (l + r) >> 1;

        root.left = buildInSegmentTree(nums, l, mid);

        root.right = buildInSegmentTree(nums, mid+1, r);

        root.sum = root.left.sum + root.right.sum;

        return root;

    }

    public void updateInSegmentTree(SegmentTreeNode root, int i, int val) {

        if(root.lc == root.rc && root.lc == i) {

            root.sum = val;

            return;

        }

        int mid = (root.lc + root.rc) >> 1;

        if(i >= root.lc && i <= mid) updateInSegmentTree(root.left, i, val);

        else updateInSegmentTree(root.right, i, val);

        root.sum = root.left.sum + root.right.sum;

    }

    public int querySum(SegmentTreeNode root, int i, int j) {

        if(root.lc == i && root.rc == j) return root.sum;

        int mid = (root.lc + root.rc) >> 1;

        if(i <= mid && j <= mid) return querySum(root.left, i, j);

        else if(i > mid && j > mid) return querySum(root.right, i, j);

        else return querySum(root.left, i, mid) + querySum(root.right, mid+1, j);

    }

}

// Your NumArray object will be instantiated and called as such:

// NumArray numArray = new NumArray(nums);

// numArray.sumRange(0, 1);

// numArray.update(1, 10);

// numArray.sumRange(1, 2);

下面附上java版segmentTree模板代码（共有两个文件：一个是SegmentTreeNode.java，另一个是SegmentTree.java。）

package cc150;

public class SegmentTreeNode {

    public int lc, rc, sum, add;

    SegmentTreeNode left, right;

    public SegmentTreeNode() {

        this.lc = 0; this.rc = 0; this.sum = 0; this.add = 0;

        this.left = null; this.right = null;

    }

    public SegmentTreeNode(int l, int r, int val) {

        this.lc = l; this.rc = r; this.sum = val; this.add = 0;

        this.left = null; this.right = null;

    }

    public static void main(String[] args) {

        // TODO Auto-generated method stub

    }

}

SegmentTreeNode.java

package cc150;

public class SegmentTree {

    public SegmentTreeNode root = null;

            int lower_bound, upper_bound;

    public SegmentTree() {

        this.root = null;

        this.lower_bound = 0; this.upper_bound = 0;

    }

    public SegmentTree(int l, int r, int []nums) {

        //@ SegmentTreeNode(left_idx, right_idx, sum).

        this.root = new SegmentTreeNode(l, r, 0);

        this.lower_bound = l; this.upper_bound = r;

        buildSegmentTree(l, r, nums, root);

    }

    public void buildSegmentTree(int l, int r, int []nums, SegmentTreeNode s) {

        SegmentTreeNode sroot = s;

        if(l > r) return;

        if(l == r) {

            sroot.sum = nums[l];

            return;

        }

        int mid = (l + r) / 2;

        sroot.left = new SegmentTreeNode(l, mid, 0);

        buildSegmentTree(l, mid, nums, sroot.left);

        sroot.right = new SegmentTreeNode(mid+1, r, 0);

        buildSegmentTree(mid+1, r, nums, sroot.right);

        sroot.sum = sroot.left.sum + sroot.right.sum;

    }

    public void updateByPoint(SegmentTreeNode sroot, int idx, int val) {

        if(idx == sroot.lc && sroot.lc == sroot.rc) {

            sroot.sum = val;

            return;

        }

        int mid = (sroot.lc + sroot.rc) / 2;

        if(idx <= mid) updateByPoint(sroot.left, idx, val);

        else updateByPoint(sroot.right, idx, val);

        sroot.sum = sroot.left.sum + sroot.right.sum;

    }

    public void updateBySegment(SegmentTreeNode sroot, int l, int r, int val) {

        if(l == sroot.lc && r == sroot.rc) {

            sroot.add += val;

            sroot.sum += val * (r - l + 1);

            return;

        }

        if(sroot.lc == sroot.rc) return;

        int len = sroot.rc - sroot.lc + 1;

        if(sroot.add > 0) {

            sroot.left.add += sroot.add;

            sroot.right.add += sroot.add;

            sroot.left.sum += sroot.add * (len - (len/2));

            sroot.right.sum += sroot.add * (len/2);

            sroot.add = 0;

        }

        int mid = sroot.lc + (sroot.rc - sroot.lc)/2;

        if(r <= mid) updateBySegment(sroot.left, l, r, val);

        else if(l > mid) updateBySegment(sroot.right, l, r, val);

        else {

            updateBySegment(sroot.left, l, mid, val);

            updateBySegment(sroot.right, mid+1, r, val);

        }

        sroot.sum = sroot.left.sum + sroot.right.sum;

    }

    static int querySum(SegmentTreeNode sroot, int i, int j) {

        if(i > j) {

            System.out.println("Invalid Query!");

            return -1;

        }

        if(i<sroot.lc || j>sroot.rc) return querySum(sroot, sroot.lc, sroot.rc);

        if(sroot.lc == i && sroot.rc == j) return sroot.sum;/*

        int len = sroot.rc - sroot.lc + 1;

        if(sroot.add > 0) {

            sroot.left.add += sroot.add;

            sroot.right.add += sroot.add;

            sroot.left.sum += sroot.add * (len - len/2);

            sroot.right.sum += sroot.add * (len/2);

            sroot.add = 0;

        }

        */

        int mid = (sroot.lc + sroot.rc) / 2;

        if(j <= mid) return querySum(sroot.left, i, j);

        else if(i > mid) return querySum(sroot.right, i, j);

        else return querySum(sroot.left, i, mid) + querySum(sroot.right, mid+1, j);

    }

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int []nums = new int[10];

        for(int i=0;i<nums.length;++i) nums[i] = i;

        SegmentTree st = new SegmentTree(0, nums.length-1, nums);

        int tmp = querySum(st.root, 0, 9);

        System.out.println(tmp);

        st.updateByPoint(st.root, 5, 7);

        System.out.println(querySum(st.root, 0, 9));

        st.updateBySegment(st.root, 3, 4, 2);

        System.out.println(querySum(st.root, 2, 7));

    }

}

SegmentTree.java

最新文章

  1. 安卓gridview 网格，多行多列实现
  2. apache日志轮询技术
  3. iOS开发－oc（菜鸟笔记）
  4. jQuery操作控件
  5. PHP处理CSV表格文件的常用操作方法是怎么样呢
  6. 排序算法FOUR:堆排序HeapSort
  7. Android 上使用 iconfont 的一种便捷方案
  8. Maximum Subarray / Best Time To Buy And Sell Stock 与 prefixNum
  9. html5 canvas 一个漫天飞雪的效果
  10. 【转】CoreData以及MagicalRecord （一）
  11. python学习之路三（文件读写）
  12. Centos7搭建kubernetes搭建
  13. HDU 2412 Farm Irrigation
  14. 【linux之bash】
  15. spring-boot整合mybatis（web mysql logback配置）
  16. Mac轻量级服务器http-server
  17. JSViews--JQuery系的MVVM框架
  18. 高通非adsp 架构下的sensor的bug调试
  19. hdu3861 强连通分量缩点+二分图最最小路径覆盖
  20. 洛谷 1192：台阶问题（递推，DP）

热门文章

  1. sequel 连接不上，命令行能连上
  2. 在非MFC程序中引用CString
  3. Kali2.0 Sqlmap清除历史扫描日志
  4. 安装Ubuntu双系统系列——安装中文输入法
  5. movzbl和movsbl
  6. bzoj1030
  7. linq .dbml转化成sql脚本
  8. tyvj1161聚会的名单（trie树）
  9. [CF 471C] MUH and House of Cards
  10. FirstOrDefault