基础算法题——树状数组 1 ：单点修改，区间查询

快来打我* 2022-12-19 14:25 124阅读 0赞

### [树状数组][Link 1] ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
![timu2][]  
![题目3][3]  
复习基础！！

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll c[1000010], n, q;
    
    ll lowbit(ll x){ 
    	return x&(-x);
    }
    
    void updata(ll x, ll v){ 
    	for(ll k=x; k<=n; k+=lowbit(k))
    		c[k] += v;
    }
    
    ll getSum(ll x){ 
    	ll sum=0;
    	for(ll k=x; k>0; k-=lowbit(k))
    		sum += c[k];
    	return sum;
    }
    
    int main(){ 
    	scanf("%lld%lld", &n, &q);
    	for(ll i=1; i<=n; i++){ 
    		ll tmp;
    		scanf("%lld", &tmp);
    		updata(i, tmp);
    	}
    	while(q--){ 
    		ll x, y, z;
    		scanf("%lld%lld%lld", &x, &y, &z);
    		if(x==1)
    			updata(y, z);
    		else
    			printf("%lld\n", getSum(z)-getSum(y-1));
    	}
    	
    	return 0;
    }

[Link 1]: https://loj.ac/problem/130
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/4407f679a3774025a37f3eaaa2ac31ab.png
[timu2]: /images/20221120/d117709715d54a129b546f02e7e21be0.png
[3]: https://img-blog.csdnimg.cn/20201108140254980.png#pic_center

发表评论取消回复

表情：

评论列表（有 0 条评论，124人围观）

还没有评论，来说两句吧...

相关阅读

相关 P3374 树状数组 1（单点修改求和）

P3374 【模板】树状数组 1 题目链接：[https://www.luogu.org/problem/P3374][https_www.luogu.org_probl

落日映苍穹つ/ 2023年08月17日 15:42/ 0 赞/ 109 阅读

相关基础算法题——树状数组 1 ：单点修改，区间查询

[树状数组][Link 1] ![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

快来打我*/ 2022年12月19日 14:25/ 0 赞/ 125 阅读

相关基础算法题——牛牛种花（高效、降维、离散化、树状数组）

牛牛种花 [题目链接][Link 1] ![题目1][1] ![题目2][2] 这道题还是挺有意思的，呵呵。 --------------------

逃离我推掉我的手/ 2022年12月13日 12:43/ 0 赞/ 111 阅读

相关树状数组模板（区间查询）

[https://www.luogu.com.cn/problem/P3374][https_www.luogu.com.cn_problem_P3374] 区间查询

浅浅的花香味﹌/ 2022年10月10日 15:55/ 0 赞/ 183 阅读

相关 HDU 1556-Color the ball（树状数组-区间修改单点查询）

Color the ball Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja

以你之姓@/ 2022年08月21日 15:00/ 0 赞/ 175 阅读

相关 POJ 2155-Matrix（二维树状数组-区间修改单点查询）

Matrix <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS</td>

墨蓝/ 2022年06月16日 03:57/ 0 赞/ 206 阅读

相关关于树状数组区间修改和查询详解

[原版介绍][Link 1] 这里我想再加上自己的理解，解释一下。现在我们需要的是把某个区间的值修改，然后查询我们设原数组为 a\[1\] a\[2\] …

心已赠人/ 2022年06月13日 01:28/ 0 赞/ 208 阅读

相关 POJ 2155 Matrix（二维树状数组+数组数组区间更新+单点查询）

Given an N\N matrix A, whose elements are either 0 or 1. A\[i, j\] means the number in t

柔光的暖阳◎/ 2022年06月11日 00:26/ 0 赞/ 166 阅读

相关模板（线段树 + 树状数组 + 单点查询 + 区间查询）eg：HDU 1754 - I Hate It

HDU 1754 - I Hate It当例题； include<cstdio> include<cstring> include<iostream>

浅浅的花香味﹌/ 2022年06月07日 04:28/ 0 赞/ 203 阅读

相关 24. 树状数组1

【题目描述】：如题，已知有N个元素组成的数列（下标从1开始计数），你需要进行下面两种操作： 1.将某一个数加上x 2.求出某区间每一个数的和【输入描述】：

红太狼/ 2021年11月26日 07:34/ 0 赞/ 238 阅读