【板子】树状数组

Description

    已知一个数列，你需要进行下面两种操作：
    1.将某区间每一个数数加上x
    2.求出某区间数值和

Input

    第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
    第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
    接下来M行每行包含2或4个整数，表示一个操作，具体如下：
    操作1： 格式：1 x k 含义：将第x个数加上k
    操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

Output

    输出包含若干行整数，即为所有操作2的结果。

Sample Input

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

Sample Output

14
16

Data

    对于30%的数据：N<=8，M<=10
    对于70%的数据：N<=10000，M<=10000
    对于100%的数据：N<=500000，M<=500000

I think

    题意：单点修改+区间查询
    实现：树状数组

Code

#include<cstdio>
using namespace std;
const int sm = 500000+10;
int n,m,f,sum,c[sm];
char ch;
void read(int &x) {
x=0,f=1,ch=getchar();
while(ch>'9'||ch<'0') { if(ch=='-')f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
x*=f;
}
int lowbit(int x) {
return x&(-x);
}
void add(int x,int b) {
while(x<=n)
c[x]+=b,x+=lowbit(x);
}
int query(int x) {
sum=0;
while(x)
sum+=c[x],x-=lowbit(x);
return sum;
}
int main() {
read(n),read(m);
for(int i=1,x;i<=n;++i)
read(x),add(i,x);
for(int i=1,a,b,ind;i<=m;++i) {
read(ind),read(a),read(b);
if(ind==1) add(a,b);
else printf("%dn",query(b)-query(a-1));// query查询的是前缀和
}
return 0;
}

Description

    已知一个数列，你需要进行下面两种操作：
    1.将某区间每一个数数加上x
    2.求出某一个数的值

Input

    第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
    第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
    接下来M行每行包含2或4个整数，表示一个操作，具体如下：
    操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
    操作2： 格式：2 x 含义：输出第x个数的值

Output

    输出包含若干行整数，即为所有操作2的结果。

Sample Input

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

Sample Output

6
10

Data

    对于30%的数据：N<=8，M<=10
    对于70%的数据：N<=10000，M<=10000
    对于100%的数据：N<=500000，M<=500000

I think

    题意：区间修改+单点查询
    实现：理解差分思想。安利这篇博客的讲解：树状数组求和的三种模型

Code

#include<cstdio>
using namespace std;
const int sm = 5e5+10;
int n,m,f,x,y,k,ind,sum,a[sm],b[sm];
char ch;
void read(int &x) {
ch=getchar(),x=0,f=1;
while(ch>'9'||ch<'0') { if(ch=='-')f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
x*=f;
}
int lowbit(int x) {
return x&(-x);
}
void modify(int x,int y) {
while(x<=n)
b[x]+=y,x+=lowbit(x);
}
int query(int x) {
sum=0;
while(x)
sum+=b[x],x-=lowbit(x);
return sum;
}
int main() {
read(n),read(m);
for(int i=1;i<=n;++i) read(a[i]);
while(m--) {
read(ind),read(x);
if(ind==1) {
read(y),read(k);
modify(x,k),modify(y+1,-k);
}
else printf("%dn",query(x)+a[x]);
}
return 0;
}

最后

以上就是糟糕故事为你收集整理的【板子】树状数组的全部内容，希望文章能够帮你解决【板子】树状数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。