题解 | #区间和#

区间和

结构体

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
typedef long long LL;

struct Node
{
    int l, r;
    LL sum;
}tr[N * 4];//线段树一般要开4倍数组
int n, m, a[N];

//通过两个子节点来相应调整父节点
void pushup(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, a[l]};
    else
    {
        tr[u] = {l, r};        
        int mid = l + r >> 1;//写成tr[u].l + tr[u].r >> 1;也是一样的
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

//单点修改
void modify(int u, int x, int v)
{
    //如果正好是那个要修改的叶子节点
    if(tr[u].l == x && tr[u].r == x) tr[u].sum += v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        //由于是单点修改，所以要么在左边要么在右边
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);//修改完记得pushup
    }
}

//区间查询
LL query(int u, int l, int r)
{
    //待查询区间完全包裹当前节点所代表的区间
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    else
    {
        LL sum = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) sum += query(u << 1, l, r);//左子树包含待查询区间 （这里写=也可以）
        if(r > mid) sum += query(u << 1 | 1, l, r);//右子树包含待查询区间
        return sum;
    }
}

int main()
{
    cin >> n >> m;    
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    build(1, 1, n);
    
	int t, x, y;
	while(m --)
	{
		scanf("%d%d%d", &t, &x, &y);
		if(t == 1) modify(1, x, y);
		else printf("%lld\n", query(1, x, y));
	}
    
    return 0;
}

数组

#include <bits/stdc++.h>

#define lson u << 1, l, mid
#define rson u << 1 | 1, mid + 1, r

using namespace std;

const int N = 1e6 + 10;
typedef long long LL;

LL tr[N * 4];
int n, m;

void pushup(int u)
{
	tr[u] = tr[u << 1] + tr[u << 1 | 1];
}

void build(int u, int l, int r)
{
	if(l == r) scanf("%lld", &tr[u]);
	else
	{
		int mid = l + r >> 1;
		build(lson), build(rson);
		pushup(u);
	}
}

void modify(int u, int l, int r, int x, int v)
{
	if(l == x && r == x) tr[u] += v;
	else
	{
		int mid = l + r >> 1;
		if(x <= mid) modify(lson, x, v);
		else modify(rson, x, v);
		pushup(u);
	}
}

LL query(int u, int l, int r, int x, int y)
{
	if(x <= l && r <= y) return tr[u];
	else
	{
		LL sum = 0;
		int mid = l + r >> 1;
		if(x <= mid) sum += query(lson, x, y);
		if(y > mid) sum += query(rson, x, y);
		return sum;
	}
}

int main()
{
	cin >> n >> m;
	build(1, 1, n);
	
	while(m --)
	{
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if(t == 1) modify(1, 1, n, x, y);
		else printf("%lld\n", query(1, 1, n, x, y));
	}
	
	return 0;
}