洛谷 P3374:树状数组模板题

【问题描述】
题目来源:https://www.luogu.com.cn/problem/P3374
如题,已知一个数列,你需要进行下面两种操作:
• 将某一个数加上 x;
• 求出某区间每一个数的和。

【输入格式】
第一行包含两个正整数 n,m,分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数,其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 个整数,表示一个操作,具体如下:
• 1 x k 含义:将第 x 个数加上 k;
• 2 x y 含义:输出区间 [x,y] 内每个数的和。

【输出格式】
输出包含若干行整数,即为所有操作 2 的结果。

【输入输出样例】
输入:
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出:
14
16

【算法分析】
本题是树状数组的模板题,即实现树状数组的经典操作“单点更新,区间查询”。关于树状数组的知识点详见:
https://blog.csdn.net/hnjzsyjyj/article/details/120559543
https://blog.csdn.net/hnjzsyjyj/article/details/120573850

【数据范围】
对于 30% 的数据,1≤n≤8,1≤m≤10
对于 70% 的数据,1≤n,m≤10^4
对于 100% 的数据,1≤n,m≤5×10^5

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5+5;
int c[maxn];
int n,m;

int lowbit(int i) {
    return (-i)&i; //返回树状数组每个c[i]所包含的元素个数
}

void update(int i,int val) { //点更新,创建树状数组c[i]
    while(i<=n) {
        c[i]+=val;
        i+=lowbit(i);  //i的后继(父结点)
    }
}

int preSum(int i) { //前缀和
    int s=0;
    while(i>0) { //树状数组的下标从1开始
        s+=c[i];
        i-=lowbit(i); //i的前驱
    }
    return s;
}

int segSum(int i,int j) { //区间和
    return preSum(j)-preSum(i-1);
}

int main() {
    scanf("%d%d",&n,&m);
    memset(c,0,sizeof(c));

    int val;
    for(int i=1; i<=n; i++) { //下标从1开始
        scanf("%d",&val);
        update(i,val); //构建树状数组
    }

    while(m--) {
        int k,u,v,x;
        scanf("%d",&k);
        if(k==1) {
            scanf("%d%d",&u,&x);
            update(u,x);
        } else {
            scanf("%d%d",&u,&v);
            printf("%d\n",segSum(u,v));
        }
    }

    return 0;
}


/*
in:
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

out:
14
16
*/



【参考文献】
https://www.luogu.com.cn/problem/P3374
https://www.luogu.com.cn/problem/solution/P3374
https://blog.csdn.net/hnjzsyjyj/article/details/120559543
https://blog.csdn.net/hnjzsyjyj/article/details/120573850
https://www.luogu.com.cn/problem/P2073
https://www.luogu.com.cn/problem/P3368
 

上一篇:DPday5 线性状态DP luogu P1091 [NOIP2004 提高组] 合唱队形


下一篇:[luogu P5129] 不可思议的迷宫 题解