线段树和树状数组

线段树、树状数组常用来解决区间上的更新以及求和问题。

梳理如下：

/***********线段树***********/
/*
    1、build_tree() 
    2、update(int idx, int val)
    3、query(int L, int R) 
*/ 
#include<iostream>
#include<cstdio>
#define MAX_SIZE 1000 
using namespace std;

void build_tree(int arr[], int tree[], int node, int left, int right){
    if(left == right){
        tree[node] = arr[left];
    }else{
        int mid = (left + right) / 2;
        int left_node  = 2 * node + 1;
        int right_node = 2 * node + 2;
        build_tree(arr, tree, left_node, left, mid);
        build_tree(arr, tree, right_node, mid+1, right);
        tree[node] = tree[left_node] + tree[right_node];
    }
}

void update(int arr[], int tree[], int node, int left, int right, int idx, int val){
    if(left == right){
        tree[node] = val;
        arr[idx] = val;
    }else{
        int mid = (left + right) / 2;
        int left_node  = 2 * node + 1;
        int right_node = 2 * node + 2;
        if(idx<=mid){
            update(arr, tree, left_node, left, mid, idx, val);
        }else{
            update(arr, tree, right_node, mid+1, right, idx, val);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }
}

int query(int arr[], int tree[], int node, int left, int right, int L, int R){
    printf("left=%d, right=%d
", left, right); 
    
    if(left == right){
        return  arr[left];
    }else if(R<left || L>right){
        return 0;
    }else if(left>=L && right<=R){
        return tree[node];
    }else{
        int mid = (left + right) / 2;
        int left_node  = 2 * node + 1;
        int right_node = 2 * node + 2;
        
        int l = query(arr, tree, left_node, left, mid, L, R);
        int r = query(arr, tree, right_node, mid+1, right, L, R);
        return l+r;
    }
}

int main(){
    int arr[] = {1, 3, 5, 7, 9, 11};
    int size = 6;
    int tree[MAX_SIZE] = {0};
    build_tree(arr, tree, 0, 0, size-1);
    for(int i=0;i<=14;i++){
        printf("tree[%d]=%d
", i, tree[i]); 
    }
    
    update(arr, tree, 0, 0, size-1, 4, 6);
    printf("
");
    for(int i=0;i<=14;i++){
        printf("tree[%d]=%d
", i, tree[i]); 
    }
    
    printf("
");
    int res = query(arr, tree, 0, 0, size-1, 2, 5);
    printf("tree[%d-%d]=%d
", 2, 5, res); 
    return 0;
}

/**********树状数组***********/ 
/*        提交地址：https://vjudge.net/problem/HDU-1166         */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int a[50005], c[50005]; //a原始数组，c树状数组

int lowbit(int x){
    return x&(-x);
}

void add(int i, int k){ //i位置上加k 
    while(i<=n){
        c[i]+=k;
        i += lowbit(i);
    } 
} 

void sub(int i, int k){
    while(i<=n){
        c[i]-=k;
        i += lowbit(i);
    }
}

int getSum(int i){ //i位置的前缀和  a[0...i]的和 
    int ans = 0;
    while(i>0){
        ans+=c[i];
        i -= lowbit(i);
    }
    return ans; 
} 

int main(){
    int T, k=1;
    cin>>T;
    while(T--){
        cin>>n;
        memset(a, 0, sizeof a);
        memset(c, 0, sizeof c);
        for(int i=1; i<=n; i++){
            cin>>a[i];
            add(i, a[i]);
        }
        string s;
        int x, y;
        printf("Case %d:
", k);
        while(cin>>s && s[0]!='E'){
            cin>>x>>y;
            if(s[0]=='Q'){
                
                cout<<getSum(y)-getSum(x-1)<<endl;
            }else if(s[0]=='A'){
                add(x, y);
            }else if(s[0]=='S'){
                sub(x, y);
            }
        }
        k++;
    }
    return 0;
}