206.Interval Sum-区间求和 I（中等题）

本文主要是介绍206.Interval Sum-区间求和 I（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

区间求和 I

题目

给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 [start, end] 。对于每个查询，计算出数组中从下标 start 到 end 之间的数的总和，并返回在结果列表中。

注意事项
在做此题前，建议先完成以下三题：线段树的构造，线段树的查询，以及线段树的修改。
样例

对于数组 [1,2,7,8,5]，查询[(1,2),(0,4),(2,4)], 返回 [9,23,20]
题解

构建线段树解题，参看205.Interval Minimum Number-区间最小数（中等题）

/*** Definition of Interval:* public classs Interval {*     int start, end;*     Interval(int start, int end) {*         this.start = start;*         this.end = end;*     }*/class SegmentTreeNode {public int start, end;public long sum;public SegmentTreeNode left, right;public SegmentTreeNode(int start, int end, long sum) {this.start = start;this.end = end;this.sum = sum;this.left = this.right = null;}
}public class Solution {/***@param A, queries: Given an integer array and an query list*@return: The result list*/public ArrayList<Long> intervalSum(int[] A, ArrayList<Interval> queries) {ArrayList<Long> result = new ArrayList<Long>();SegmentTreeNode root = new SegmentTreeNode(0,A.length-1,0);create(A,root);//生成线段树for (int i=0;i<queries.size();i++){Interval interval = queries.get(i);result.add(getSum(root,interval.start,interval.end));}return result;}private void create(int[] A, SegmentTreeNode root){if (root.start == root.end){root.sum = A[root.start];return;}int mid = (root.start + root.end) / 2;root.left = new SegmentTreeNode(root.start,mid,0);root.right = new SegmentTreeNode(mid+1,root.end,0);create(A,root.left);create(A,root.right);root.sum = root.left.sum + root.right.sum;}private long getSum(SegmentTreeNode root, int start, int end){if (root.start == start && root.end == end){return root.sum;}long leftSum = 0;long rightSum = 0;int mid = (root.start + root.end) / 2;if (mid >= start){leftSum = getSum(root.left,start,Math.min(mid,end));}if (mid < end){rightSum = getSum(root.right,mid>=start?mid+1:start,end);}return leftSum + rightSum;}
}