线段树（数组计算机）

àì夳堔傛蜴生んèń 2021-11-11 16:46 101阅读 0赞

**例题：**

Problem Description

bLue 有一个神器的机器，这个机器可以读入一个数组，并按照用户要求快速地进行数组的处理和计算，它支持如下两种操作：  
操作 1：把数组中第 p 个元素的值增加 v。  
操作 2：计算数组中 \[l, r\] 区间内所有数的和。  
这个机器就是这么的神奇，但是 bLue 的计算机坏掉了，你能帮他修一下吗？

Input

输入数据有多组（数据组数不超过 20），到 EOF 结束。  
对于每组数据：  
第 1 行输入一个整数 n (1 <= n <= 10^5)，表示数组中元素的个数。  
第 2 行输入 n 个用空格隔开的整数 ai (1 <= ai <= 10^10)，表示初始输入到计算机中的数组。  
第 3 行输入一个整数 q (1 <= q <= 50000)，表示用户的操作次数。  
接下来 q 行，每行输入先输入 1 个整数，表示操作类型，根据不同的操作类型：  
如果类型为 1，则紧接着输入 2 个用空格隔开的整数 p (1 <= p <= n) 和 v (1 <= v <= 10^10)，表示要把数组中第 p 个数的值增加 v。  
如果类型为 2，则紧接着输入 2 个用空格隔开的整数 l, r (1 <= l <= r <= n)，表示要计算区间 \[l, r\] 内所有数的和（数组下标从 1 开始）。

Output

对于每组数据中的每次类型为 2 的操作，输出 1 行，包含一个整数，表示计算出的和。

Sample Input

5  
1 2 3 4 5  
5  
2 1 2  
2 1 5  
1 4 10  
2 4 5  
2 1 5

Sample Output

3  
15  
19  
25

#include<bits/stdc++.h>
    using namespace std;
    
    struct node
    { 
        long long val;//此处必须是long long类型，因为要存long long型值
    }tree[500001];
    long long data[500001];
    
    void build(int root, int left, int right)
    { 
        if(left == right)
        { 
            tree[root].val = data[left];
            return ;
        }
        int mid = (left + right) / 2;
        build(root * 2 + 1, left, mid);
        build(root * 2 + 2, mid + 1, right);
        tree[root].val = tree[root * 2 + 1].val + tree[root * 2 + 2].val;
    }
    
    void updata(int root, int left, int right, long long pos, long long val)
    { 
        if(left == right)
        { 
            tree[root].val += val;
            return ;//找到叶子结点以后就不能继续递归下去了因此return
        }
        int mid = (left + right) / 2;
        if(pos <= mid)
        { 
            updata(root * 2 + 1, left, mid, pos, val);
        }
        else
        { 
            updata(root * 2 + 2, mid + 1, right, pos, val);
        }
        tree[root].val = tree[root * 2 + 1].val + tree[root * 2 + 2].val;//更新
    }
    
    long long query(int root, int left, int right, long long qleft, long long qright)
    { 
        long long res = 0;//注意这里也是long long类型
        if(qleft <= left && qright >= right)
        { 
            return tree[root].val;
        }
        int mid = (left + right) / 2;
        if(qleft <= mid)
        { 
            res += query(root * 2 + 1, left, mid, qleft, qright);
        }
        if(qright > mid)
        { 
            res += query(root * 2 + 2, mid + 1, right, qleft, qright);
        }
        return res;
    }
    
    int main(void)
    { 
        int n;
        while(~scanf("%d", &n))
        { 
            memset(tree, 0, sizeof(tree));
            memset(data, 0, sizeof(data));
            for(int i = 0; i < n; i++)
            { 
                scanf("%lld", &data[i]);
            }
            build(0, 0, n - 1);
            int q;
            scanf("%d", &q);
            long long x, y, z;
            while(q--)
            { 
                scanf("%lld %lld %lld", &x, &y, &z);
                if(x == 1)
                { 
                    updata(0, 0, n - 1, y - 1, z);
                }
                else if(x == 2)
                { 
                    printf("%lld\n", query(0, 0, n - 1, y - 1, z - 1));
                }
            }
        }
    
        return 0;
    }