动态求连续区间和_(线段树，树形数组）

原题链接：1264. 动态求连续区间和 - AcWing题库

题意：一个数组，两种操作，求区间和或改某个数

思路

数组是动态变化的，前缀和不适用

同样要预处理来减小时间复杂度，要求的是一个区间的和，且要保证每个数的改变要影响到预处理的区间和，如果前缀和每次都是$O(n)$ ，用树状数组可以实现二分，即$O(logn)$

最高为$O(mlogn)$的复杂度

实际上使用了线段树的模板

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 100010;
 
int n, m;
int w[N]; //记录初始数组
 
struct Node{
    int l, r;
    int sum;
}tr[4 * N];
//四倍空间
 
 
//数组前面反而是根节点
void push_up(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
 
 
void build(int u, int l, int r)
{
    //二分到最后是叶节点
    if(l == r) tr[u] = {l, r, w[r]};
    else
    {
        //二分存下所有
        tr[u] = {l, r};
        
        int mid = (l + r) >> 1;
        //左边构建
        build(u << 1, l, mid);
        //右边构建
        build(u << 1 | 1, mid + 1, r);
        
        //建完更新结点
        push_up(u);
    }
}
 
int query(int u, int l, int r)
{
    //如果左右已经完全被包含了,那就计算返回结果
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    
    //否则递归分区域计算，只要有交集，就不断地分，一直到分出来的区域被包含
    int mid = (tr[u].l + tr[u].r) >> 1;
    
    int sum = 0;
    //会分出多个被包含的不重复的区域，所以每次累加，最后返回sum
    if(mid >= l) sum += query(u << 1, l, r);
    
    if(r >= mid + 1) sum += query(u << 1 | 1, l, r);
    
    return sum;
}
 
 
void modify(int u, int x, int y)
{
    //叶子节点
    if(tr[u].l == tr[u].r) tr[u].sum += y;
    else
    {
        //在左边改左节点，在右边就改右边
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) modify(u << 1, x, y);
        else modify(u << 1 | 1, x, y);
        
        //改完更新
        push_up(u);
    }
}
 
 
int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) cin >> w[i];
    //初始化
    build(1, 1, n);
    
    while(m --)
    {
        int k, a, b;
        
        cin >> k >> a >> b;
        
        if(!k) cout << query(1, a, b) << endl;
        else modify(1, a, b);
    }
    
    return 0;
}