109徐守佳

用户名：dotcpp0787174

访问量：995

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	919
经　　验	3474
参赛次数	1
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1545-Balanced Lineup] RMQ
浏览：21

[信息学奥赛一本通T1547-区间和]-分块写法
浏览：15

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

[信息学奥赛一本通T1547-区间和]-线段树做法

　　作者: 109徐守佳　　　　发表时间：2024-09-27 11:49:38 浏览：21　|　评论：0　

原题链接：信息学奥赛一本通T1547-区间和

![](/image_editor_upload/20240927/20240927115332_82505.jpg)
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N =  2 *1e5 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
int a[N];
struct node //线段树节点
{
    int l,r; //存储节点的左右区间值
    LL v; //存储该节点区间的区间和
}tr[4*N]; //开4倍大小
void pushup(int u) //又子节点更新父节点操作
{
    tr[u].v = tr[u<<1].v + tr[u<<1|1].v; 
	//父节点区间和等于左右节点之和
}
void build(int u,int l,int r)
{
    if(l==r) tr[u] = {l,r,a[r]}; //建树结束条件
    else
    {
        tr[u] = {l,r};//给节点左右区间赋值
        int mid = l+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].v += v; 
	//找到了该点，该点加上b
    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); //退出时随便更新该节点信息
    }
}
LL quary(int u,int l,int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v; 
	//查询区间完全包含该节点区间，直接返回该节点区间和
    else
    {
	//否则就加上分别递归左右子节点保存答案和
        int mid = tr[u].l+tr[u].r >> 1;
        LL res =0;
        if(l <= mid) res += quary(u<<1,l,r);
        if(r > mid) res += quary(u<<1|1,l,r);
        return res;
    }
}
void solve()
{
    cin>>n>>m;
    build(1,1,n); //建立1~n区间的树
    while (m--)
    {
        int k,a,b;
        cin>>k>>a>>b;
        if(k==0)
        {
            modify(1,a,b);
        }
        else
        {
            cout<<quary(1,a,b)<<endl;
        }
    }
    
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    // int _; cin>>_; while(_--){}
    solve();
    return 0;
}

```
![](https://pic.imgdb.cn/item/66f645d9f21886ccc0c26f2a.gif)

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

109徐守佳

TA的其他文章

你可能喜欢

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C二级辅导-分段函数（C语言代码）

[信息学奥赛一本通T1547-区间和]-线段树做法

评论区

精彩推荐

C语言训练-字符串正反连接（C语言代码）

C语言训练-最大数问题（C语言代码）

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

输出正反三角形（C语言代码）

C语言训练-求函数值（C语言代码）

淘淘的名单（C语言代码）

WU-整除问题（C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C二级辅导-分段函数 （C语言代码）

[信息学奥赛一本通T1547-区间和]-线段树做法

评论区

精彩推荐

C语言训练-字符串正反连接 （C语言代码）

C语言训练-最大数问题 （C语言代码）

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

输出正反三角形 （C语言代码）

C语言训练-求函数值 （C语言代码）

淘淘的名单 （C语言代码）

WU-整除问题 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

Tom数（C语言代码）

C二级辅导-分段函数（C语言代码）

　　评论区

C语言训练-字符串正反连接（C语言代码）

C语言训练-最大数问题（C语言代码）

输出正反三角形（C语言代码）

C语言训练-求函数值（C语言代码）

淘淘的名单（C语言代码）

WU-整除问题（C++代码）