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

浅浅的花香味﹌ 2022-10-10 15:55 231阅读 0赞

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

#include <iostream>
    using namespace std;
    #define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
    int n,m;
    const int N = 5e5+10;
    int c[N];
    
    int lowbit(int x) { return x&-x;} // 计算父亲节点
    void update(int i, int x)
    { 
        while(i<=n){ 
            c[i] += x; // 减法 c[i]-=x;
            i += lowbit(i);
        }
    }
    int getsum(int i)
    { 
        int sum = 0;
        while(i){ 
            sum += c[i];
            i -= lowbit(i);
        }
        return sum;
    }
    int main()
    { 
        ios;
        cin >> n >> m;
        for(int i = 1; i<= n; i++){ 
            int tmp; cin >> tmp;
            update(i, tmp);
        }
        while (m--)
        { 
            int num, l, r;
            cin >> num >> l >> r;
            if(num==1) update(l,r);
            else cout << getsum(r) - getsum(l-1) << endl;
        }
    }

[https_www.luogu.com.cn_problem_P3374]: https://www.luogu.com.cn/problem/P3374

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关树状数组求区间和

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

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

相关树状数组模板

胡说：树状数组和堆都是我特别喜欢的数据结构，对我来说，编起来的节奏就是和别的不一样，如果把编程说是一首歌，这两种就是明朗轻快的类型。题目：问题描述有n个格子，

我不是女神ヾ/ 2022年08月27日 10:42/ 0 赞/ 213 阅读

相关树状数组模板

include <stdio.h> include <string.h> int n, c[100004]; int lo

阳光穿透心脏的1/2处/ 2022年06月16日 01:58/ 0 赞/ 251 阅读

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

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

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

相关模板（线段树 + 树状数组 + 区间修改 + 区间查询）eg：POJ 3468 - A Simple Problem with Integers

include<cstdio> include<algorithm> include<cstring> include<iostream>

太过爱你忘了你带给我的痛/ 2022年06月07日 04:35/ 0 赞/ 215 阅读

相关树状数组模板

1. int lowbit(int t) 2. `{` 3. `return t&(-t);` 4. `}` 1. `void add(int x,int y)`

水深无声/ 2022年05月31日 10:42/ 0 赞/ 276 阅读

相关 (模板)树状数组模板

include <iostream> using namespace std; const int MAX_N= 10010; int C[MA

Dear 丶/ 2022年02月16日 05:41/ 0 赞/ 385 阅读

相关树状数组模板

//树状数组 struct Bit { vector<int> a; int sz; void ini

ゞ浴缸里的玫瑰/ 2021年09月19日 05:46/ 0 赞/ 405 阅读

相关树状数组模板

\define lowbit(x) (x&(-x)) int c\[Max\], n;//n为元素个数 void add(int x, int v)//单点给元素+

朱雀/ 2021年07月16日 14:44/ 0 赞/ 475 阅读