线段树

· · 算法·理论

线段树

代码（建树）：

void create(int l,int r,int u) {
    if(l==r) {
        a[u]=x[l];
        return;
    } int mid=l+r>>1;
    create(l,mid,u<<1), create(mid+1,r,u<<1|1);
    a[u]=a[u<<1]+a[u<<1|1];
} //to create a tree

代码（查询）

int query(int l,int r,int u,int s,int t) {
    if(s>r||t<l) return 0; 
    if(l>=s&&r<=t) return a[u];
    int mid=(l+r)>>1;
    return query(l,mid,u<<1,s,t)+query(mid+1,r,u<<1|1,s,t); 
}

代码（修改）

void upd(int l,int r,int u,int i,int c) {
    a[u]+=c;
    if(l==r) return;
    int mid=l+r>>1;
    if(mid>=i) upd(l,mid,u<<1,i,c);
    else upd(mid+1,r,u<<1|1,i,c);
}

完整代码：

#include<iostream>
#define int long long
using namespace std;
const int N = 1e6+7;
int a[N<<2],x[N];
void create(int l,int r,int u) {
    if(l==r) {
        a[u]=x[l];
        return;
    } int mid=l+r>>1;
    create(l,mid,u<<1), create(mid+1,r,u<<1|1);
    a[u]=a[u<<1]+a[u<<1|1];
} //to create a tree 
int query(int l,int r,int u,int s,int t) {
    if(s>r||t<l) return 0; 
    if(l>=s&&r<=t) return a[u];
    int mid=(l+r)>>1;
    return query(l,mid,u<<1,s,t)+query(mid+1,r,u<<1|1,s,t); 
}
//this function refers to query the [l,r] period on the tree whose root is u.
void upd(int l,int r,int u,int i,int c) {
    a[u]+=c;
    if(l==r) return;
    int mid=l+r>>1;
    if(mid>=i) upd(l,mid,u<<1,i,c);
    else upd(mid+1,r,u<<1|1,i,c);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>x[i];
    create(1,n,1);
    while(m--) {
        int op,e,f;
        cin>>op>>e>>f;
        if(op==2) cout<<query(1,n,1,e,f)<<'\n';
        else upd(1,n,1,e,f);
    }
    return 0;
}

输入

16 7
9 1 3 0 4 5 7 6 8 0 3 3 2 8 1 4
1 6 9
2 1 8
1 11 3
2 5 11
1 7 5
1 1 10
2 7 15

输出：

44
45
46

例题：https://www.luogu.com.cn/problem/P4513

代码：https://www.codepaste.cn/#/cd/fc2100ac-9167-46b3-9473-a809bf772f5d