【深进1.例1】求区间和

链接

显然,这是一个求和线段树

那也不用过多赘述了

#include<bits/stdc++.h>
using namespace std;
struct node{
    vector<int>tree;
    int n;
    void build(vector<int>&data,int root,int left,int right){
        if(left==right){
            tree[root]=data[left];
            return;
        }
        int mid=left+(right-left)/2;
        build(data,2*root,left,mid);
        build(data,2*root+1,mid+1,right);
        tree[root]=tree[2*root]+tree[2*root+1];
    }
    int query(int root,int left,int right,int ql,int qr){
        if(ql>right||qr<left){
            return 0;
        }
        if(ql<=left&&qr>=right){
            return tree[root];
        }
        int mid=left+(right-left)/2;
        int left_sum=query(2*root,left,mid,ql,qr);
        int right_sum=query(2*root+1,mid+1,right,ql,qr);
        return left_sum+right_sum;
        
    }
    node(vector<int>data){
        n=data.size()-1;
        tree.resize(4*(n+1));
        build(data,1,1,n);
    }
};
int main(){
    int n;
    cin>>n;
    vector<int>data(n+1);
    for(int i=1;i<=n;i++){
        cin>>data[i];
    }
    node tree(data);
    int m;
    cin>>m;
    vector<int>l(m+1),r(m+1);
    for(int i=1;i<=m;i++){
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<=m;i++){
        cout<<tree.query(1,1,n,l[i],r[i])<<endl;
    }
}

时间复杂度:O(n + m log n)

空间复杂度:O(log n)