c++树状数组与线段树模板

本文主要是介绍c++树状数组与线段树模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

输入输出样例

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5 
0 1 3
0 4 8 
1 7 5
0 4 8

输出效果

11
30
35

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int w[100006];
struct node{
    int l,r;
    int sum;

}aa[400006];

void pushup(int u){
    aa[u].sum = aa[u*2].sum+aa[u*2+1].sum;
}

void build(int u,int l,int r){
    if(l==r) aa[u]={l,r,w[l]};
    else{
        aa[u]={l,r};
        int mid = (l+r)/2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}
int query(int u,int l,int r){
    if(l<=aa[u].l && aa[u].r<=r) return aa[u].sum;
    int mid = (aa[u].l+aa[u].r)/2;
    int sum = 0;
    if(l<=mid) sum+=query(u*2,l,r);
    if(r>mid) sum+= query(u*2+1,l,r);
    return sum;
}
void modify(int u,int x,int v){
    if(aa[u].l == aa[u].r) aa[u].sum += v;
    else{
        int mid =(aa[u].l+aa[u].r)/2;
        if(x<=mid) modify(u*2,x,v);
        else modify(u*2+1,x,v);
        pushup(u);
    }
}

int main()
{
    cin >> n >> m;
    int x,a,b;
    for(int i =11;i<=n;i++) cin >> w[i];
    build(1,1,n);
    while(m--){
        cin >> x >> a >> b;
        if(!x) cout << query(1,a,b) << endl;
        else modify(1,a,b);
    }
    return 0;

}

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
//#define debug freopen("input.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,M;
int arr[maxn];
int tr[maxn];

int lowbit(int x){
    return x&-x;
}
void add(int idx,int v){
    for(int i =idx;i<=N;i+=lowbit(i)) tr[i]+=v;
}
ll query(int r){
    ll sum = 0;
    for(int i= r;i>=1;i-= lowbit(i)) sum+=tr[i];
    return sum;
}
int main()
{
    //debug
    ios;
    cin >> N >> M;
    for(int i =1;i<=N;i++) cin >> arr[i];
    for(int i =1;i<=N;i++) add(i,arr[i]);
    while(M--){
        int k,a,b;
        cin >> k >> a >> b;
        if(k==0){
            cout << query(b) - query(a-1) << endl;
        }else{
            add(a,b);
        }
    }
    return 0;
}

这篇关于c++树状数组与线段树模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！