树状数组求区间和

怼烎@ 2022-10-01 00:51 175阅读 0赞

求数组区间和：

如 1 2 3 4 5

\#include <iostream>

\#include <string>

\#include <cstring>

\#define lowbit(x) ((x)&(-(x)))

using namespace std;

int c\[524288+1\],n,m,x,y,z;

void update(int x,int k)

\{

for(int i=x;i<=n;i+=lowbit(i))

c\[i\]+=k;   //子节加k，父节点也要加k;

\}    //将x节点的所有上一级节点都加k;  即整体更新；

int sum(int x)//求的是第一个到第x个的值之和；

\{

int ans=0;

for(int i=x;i>0;i-=lowbit(i))

ans+=c\[i\];

return ans;

\}

int main()

\{

cin >> n >> m ;   //m是操作次数；

for(int i=1;i<=n;i++)

\{

cin >> x;  /就是/输入数组1 2 3 4 5；

update(i,x);//可以理解为构造树状数组c\[i\]

\}

for(int i=1;i<=m;i++)

\{

cin >> x >> y >> z;  //求区间y到 z的和；

if(x==1)  update(y,z);   x等于1就是更改节点；等于2就是求和；

if(x==2)cout << sum(z)-sum(y-1) << endl;

\}

return 0;

\}

刚学树状数组，看到这里的时候懵了。经过询问，发现，原来在程序运行时，数据用的都是补码，于是解决了

int Lowbit(x)

\{

return x&(-x);

\}

如:

x =1： 1 &－１（设位数为８）0000 0001 & 1111 1111 = 1

x = 6:6 & -6   00000110

&1111 1010 = 2

总结一下，其实就是：

求出2^p(其中p: x 的二进制表示数中，从右向左数第一个1的下标，且下标是

从零开始)，如6的node\[i\].val二进制表示为110，向左数第1个1的下标是1，即p=1，

故 Lowbit(6) = 2^1 = 2 。

发表评论取消回复

表情：

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

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

相关阅读

相关区间求不重复值的和（树状数组求解）

**题目：**[Galahad][] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a...

柔情只为你懂/ 2024年04月19日 14:46/ 0 赞/ 54 阅读

相关 hdu1166敌兵布阵树状数组&线段树单点更新求区间和

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

偏执的太偏执、/ 2024年02月17日 19:42/ 0 赞/ 39 阅读

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

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

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

相关树状数组求区间和

求数组区间和：如 1 2 3 4 5 \include <iostream> \include <string> \include <cstring> \defin

怼烎@/ 2022年10月01日 00:51/ 0 赞/ 176 阅读

相关 POJ 1195-Mobile phones(二维树状数组-区间更新区间查询)

Mobile phones <table> <tbody> <tr> <td><strong>Time Limit:</strong> 5000MS</

秒速五厘米/ 2022年08月21日 15:54/ 0 赞/ 167 阅读

相关 HDU 5480 Conturbatio（二维树状数组维护区间和）

问题描述在一个n \\times mn×m的国际象棋棋盘上有很多车(Rook)，其中车可以攻击他所属的一行或一列，包括它自己所在的位置。现在还有很多询问，每次询问给

布满荆棘的人生/ 2022年08月08日 20:28/ 0 赞/ 151 阅读

相关区间查询（树状数组之差点问线问题）

1110: 区间查询时间限制: 2 Sec 内存限制: 32 MB 提交: 162 解决: 62 [提交][Link 1] [状态][Link 2] 题目描

缺乏、安全感/ 2022年08月05日 13:08/ 0 赞/ 170 阅读

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

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

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

相关树状数组求逆序数模板

以前求逆序数都是用的归并排序，现在发现树状数组求逆序数更简单，常数更小，留个板子，数值较大时需要离散化，用map实更简单，入门参考[https://www.cnblogs.c

忘是亡心i/ 2022年05月15日 18:56/ 0 赞/ 226 阅读

相关动态规划（数组区间）---数组区间和

数组区间和 [303. Range Sum Query - Immutable (Easy)][303. Range Sum Query - Immutable _Eas

Myth丶恋晨/ 2021年11月29日 07:58/ 0 赞/ 316 阅读