Lintcode206 Interval Sum solution 题解
发布在LINTCODE2018年2月8日view:255移动开发
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers[start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

Notice:We suggest you finish problem Segment Tree Build,Segment Tree Query and Segment Tree Modify first.

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

【注】:在做此题前,建议先完成以下三题:线段树的构造,线段树的查询,以及线段树的修改。

【题目链接】

www.lintcode.com/en/problem/interval-sum/

【题目解析】

此题可使用区间树解决。注意interval各有一部分处于root左侧和右侧的问题。

【参考答案】

www.jiuzhang.com/solutions/interval-sum/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏