我之前学过线段树，掌握的不是很牢固，而这道题是线段树，为了加深记忆，所以还是觉得有必要记录下来，就当是对线段树的一个复习。

题意：

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

样例：

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

1.解题思路

  这道题用线段树数做起来不是很难，同时时间复杂度也不是很高。由于楼主之前学过线段树，所以这里不再详细的讲解什么是线段树。
  我们在构建线段树时，向线段树的每一个节点加一个属性--sum，用来表示当前节点的范围的数值总和。然后在使用线段树的查询就可以得到我们想要的值了。

(1).构建线段树

private SegmentTreeNode build(int A[], int start ,int end) {
        SegmentTreeNode node = new SegmentTreeNode(start, end, A[0]);
        if(node.start == node.end) {
            node.sum = A[start];
            return node;
        }
        int mid = (node.start + node.end) / 2;
        node.left = build(A, start, mid);
        node.right = build(A, mid + 1, end);
        node.sum = node.left.sum + node.right.sum;
        return node;
    }

(2).查询线段树

private long query(SegmentTreeNode node, int start , int end) {
        if(start > end) {
            return 0;
        }
        if(node.start == start && node.end == end) {
            return node.sum;
        }
        int mid = (node.start + node.end) /  2;
        if(end <= mid) {
            return query(node.left, start, end);
        }
        else if(start > mid) {
            return query(node.right, start, end);
        }else {
            return query(node.left, start, mid) + query(node.right, mid + 1, end);
        }
    }

2.代码

public List<Long> intervalSum(int[] A, List<Interval> queries) {
        List<Long> list = new ArrayList<>();
        if(A.length == 0 || queries.size() == 0) {
            return list;
        }
        SegmentTreeNode node = build(A, 0, A.length - 1);
        
        for(int i = 0; i < queries.size(); i++) {
            list.add(query(node, queries.get(i).start, queries.get(i).end));
        }
        return list;
    }
    //构建线段树
    private SegmentTreeNode build(int A[], int start ,int end) {
        SegmentTreeNode node = new SegmentTreeNode(start, end, A[0]);
        if(node.start == node.end) {
            node.sum = A[start];
            return node;
        }
        int mid = (node.start + node.end) / 2;
        node.left = build(A, start, mid);
        node.right = build(A, mid + 1, end);
        node.sum = node.left.sum + node.right.sum;
        return node;
    }
    //查询线段树
    private long query(SegmentTreeNode node, int start , int end) {
        if(start > end) {
            return 0;
        }
        if(node.start == start && node.end == end) {
            return node.sum;
        }
        int mid = (node.start + node.end) / 2;
        if(end <= mid) {
            return query(node.left, start, mid);
        }
        else if(start > mid) {
            return query(node.right, start, end);
        }else {
            return query(node.left, start, mid) + query(node.right, mid + 1, end);
        }
    }