模板（线段树 + 树状数组 + 单点查询 + 区间查询）eg：HDU 1754 - I Hate It

浅浅的花香味﹌ 2022-06-07 04:28 219阅读 0赞

HDU 1754 - I Hate It当例题；

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define lson l, m, rt<<1//<<左移运算符
    #define rson m+1, r, rt<<1|1
    
    using namespace std;  
    
    const int treen = 200000 + 10;  
    int tree[treen << 2];
    
    void pushUP(int rt) {  //向上更新
        tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);
    }
    
    void build(int l, int r, int rt) {  
        if(l == r) {
       //如果左边=右边边界，说明这个已经是一个点了，比如[1,1]闭区间里只有1个数
            scanf("%d", &tree[rt]);//然后更细端点值，我们这里称他为叶子
            return;
        }
        int m = (l+r)>>1;
        build(lson);//如果没有到叶子的话，继续往下分，这里称为左儿子
        build(rson);//右儿子
        pushUP(rt);//吧叶子更新后，上面的节点并没有更新，向上更新
    }
    
    void updata(int p, int add, int l, int r, int rt) {  
        if(l == r) {
            tree[rt] = add;//在原数基础上加减的话用+=(全部用+=，需要减的话传入的时候变为负的）
                            //更改原数的话，用=
            return;
        }
        int m = (l+r)>>1;//分为一半，二分原理去更新，更快
        if(p <= m) updata(p, add, lson);//更新的点在左边
        else updata(p, add, rson);//右边
        pushUP(rt);//更新后需要向上更新
    }
    
    int query(int L, int R, int l, int r, int rt) {  
        if(L<=l && r<=R) {
       //查询的区间正好在此区间的内的话，直接返回节点值，也就是要求的和
                            //(节点放的是下面数的总和)
            return tree[rt];
        }
        int m = (r+l)>>1;//同上
        int ret = 0;
        if(L <= m) ret = max(query(L, R, lson), ret);
        if(R > m) ret = max(query(L, R, rson), ret);
        return ret;//返回最大的值
    }
    
    int main() {  
        int n, m;
        while(~scanf("%d %d", &n, &m)) {
            memset(tree, 0, sizeof(tree));
            build(1, n, 1);//建树
            for(int i = 0; i < m; i++) {
                char op;
                int a, b;
                cin >> op >> a >> b;
                if(op == 'U') {
                    updata(a, b, 1, n, 1);//更新
                }else {
                    printf("%d\n", query(a, b, 1, n, 1));//查询
                }
            }
        }
        return 0;
    }

树状数组 [解释][Link 1]  
一定要理解之后才看的懂

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    
    using namespace std;  
    
    typedef long long ll;  
    const int  maxn = 200000 + 100;;  
    int h[maxn], a[maxn];  
    int n, m;  
    
    inline int lowbit(int x) {  //给出下一个需要操作数组的下标
        return x&(-x);
    }
    inline void updata(int x) {  
        while(x <= n) {
       //x的值是变化的，直到需要更新的更新了
            h[x] = a[x];
            for(int i = 1; i < lowbit(x); i<<=1)
                h[x] = max(h[x], h[x-i]);
            x += lowbit(x);
        }
    }
    int findans(int begin, int end) {
        int ans = 0;
        while(end >= begin) {
            ans = max(ans, a[end]);
            end--;
            for(; end-lowbit(end)>=begin; end-=lowbit(end))
            ans = max(ans, h[end]);
        }
        return ans;
    }
    int main() {  
        while(~scanf("%d %d", &n, &m)) {
            for(int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
                updata(i);//每有一个数值输入就需要更新树状数组
            }
            char ch;
            int x, y;
            for(int i = 0; i < m; i++) {
                cin >> ch >> x >> y;
                if(ch == 'Q') {
                    printf("%d\n", findans(x, y));
                }else if(ch == 'U') {
                    a[x] = y;
                    updata(x);//修改后就需要更新
                }
            }
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/xiao_bai_9527/article/details/73691142