Lintcode---区间求和 I

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

注意事项

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

您在真实的面试中是否遇到过这个题？

Yes

样例

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

挑战

O(logN) time for each query

思路：看到区间求和问题，符合线段树适用连续区间统计或者查询的问题。所以，考虑构建合适的线段树来求解。

题目类型与区间最小数问题类似。先构建对应的线段树，然后查询；

vector<int>& A一定要加引用，否则，每次调用函数都要拷贝容器,很耗时！！！

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
/*
思路：看到区间求和问题，符合线段树适用连续区间统计或者查询的问题。所以，考虑构建合适的线段树来求解。
      题目类型与区间最小数问题类似。先构建对应的线段树，然后查询；
*/ 
 
class SegmentTreeNode33{  
public:
    int start,end;  
    long long sum;  
    SegmentTreeNode33* right,*left;  
    SegmentTreeNode33(int start,int end){  
        this->start=start;  
        this->end=end;  
        this->sum=0;  
        this->left=this->right=NULL;
    }  
};


class Solution { 
public:
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    
    //线段树构造；
    SegmentTreeNode33* build(int start,int end,vector<int>& A){
    
        //vector<int>& A一定要加引用，否则，每次调用函数都要拷贝容器很耗时！！！
        if(start>end)  
            return NULL;  
        SegmentTreeNode33* root= new SegmentTreeNode33(start,end);  
        if(start!=end){  
            int mid=start+(end-start)/2;  
            root->left=build(start,mid,A);  
            root->right=build(mid+1,end,A);  
            root->sum=root->left->sum+root->right->sum;  
        }else  
            root->sum=A[start];  
        return root;      
    }
    
    
    //线段树查询；
    long long query(SegmentTreeNode33* root,int start,int end){  
        if(root==NULL||start>end)  
            return 0;  
        if(start<=root->start&&end>=root->end)  
            return root->sum;  
        int mid=(root->start+root->end)/2;  
        if(start>mid)  
            return query(root->right,start,end);  
        else if(end<mid+1)  
            return query(root->left,start,end);  
        else  
            return query(root->right,mid+1,end)+query(root->left,start,mid);      
    }
    
    
    
    vector<long long> intervalSum(vector<int> &A, vector<Interval> &queries) {
        // write your code here
        vector<long long> res;  
        SegmentTreeNode33* root=build(0,A.size()-1,A);  
        for(Interval qujian:queries){
            res.push_back(query(root,qujian.start,qujian.end));
        }
        return res;                                     
    }
};