109徐守佳

用户名：dotcpp0787174

访问量：1123

签　名：

想AC的我戴上了WA面具

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

　　自我简介：

TA的其他文章

[蓝桥杯2024年第十五届决赛真题-旋转九宫格] 测试数据量最大的一集
浏览：499

[信息学奥赛一本通T1547-区间和]-树状数组写法
浏览：33

[信息学奥赛一本通T1471-Phone List] Trie字典树做法
浏览：26

你可能喜欢

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

　　作者: 109徐守佳　　　　发表时间：2024-09-27 11:49:38 浏览：23　|　评论：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的其他文章

你可能喜欢

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

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

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

P1001 （C++代码）

C二级辅导-同因查找（C语言代码）

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

评论区

精彩推荐

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

A+B for Input-Output Practice (VII) （C++代码）

拆分位数（C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

【蟠桃记】（C语言代码）

简单的a+b （C语言代码）

1071题解

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

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

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

109徐守佳

TA的其他文章

你可能喜欢

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

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

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

P1001 （C++代码）

C二级辅导-同因查找 （C语言代码）

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

评论区

精彩推荐

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

A+B for Input-Output Practice (VII) （C++代码）

拆分位数 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

【蟠桃记】 （C语言代码）

简单的a+b （C语言代码）

1071题解

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

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

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

C二级辅导-同因查找（C语言代码）

　　评论区

拆分位数（C语言代码）

【蟠桃记】（C语言代码）