树状数组的变形（差分+数组数组）

ゝ一世哀愁。 2022-10-11 00:44 119阅读 0赞

暴力求解是不行的

注意到差分后的一些性质

1 , 6 , 8 , 5 , 10 \{1,6,8,5,10\} 1,6,8,5,10，对应差分数组 1 , 5 , 2 , − 3 , 5 \{1,5,2,-3,5\} 1,5,2,−3,5

区间\[2,4\] + 2

1 , 8 , 10 , 7 , 10 \{1,8,10,7,10\} 1,8,10,7,10，对应差分数组 1 , 7 , 2 , − 3 , 3 \{1,7,2,-3,3\} 1,7,2,−3,3

就是 a \[ 2 \] + 2 a\[2\]+2 a\[2\]\+2 ， a \[ 5 \] − 2 a\[5\]-2 a\[5\]−2

#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;
            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;
        int last = 0, now;
        for(int i = 1; i<= n; i++){ 
            
            cin >> now;
            update(i, now-last);
            last = now;
        }
        while (m--)
        { 
            int op;cin >> op;
            if(op==1){ 
                int x, y, k; cin >> x >> y >> k;
                update(x,k);
                update(y+1,-k);
            }else{ 
                int x; cin >> x;
                cout << getsum(x) << endl;
            }
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关差分数组

include<bits/stdc++.h> using namespace std; define ll long long const ...

雨点打透心脏的1/2处/ 2024年04月18日 09:43/ 0 赞/ 21 阅读

相关差分数组的使用

一、问题现在，输入一个数组 `nums`，然后又要求给区间 `nums[2..6]` 全部加 1，再给 `nums[3..9]` 全部减 3，再给 `nums[0..4

绝地灬酷狼/ 2024年04月01日 16:30/ 0 赞/ 25 阅读

相关【算法】差分数组

目录 1.概述 2.代码实现 3.应用 > 本文参考： > [LABULADONG 的算法网站][LABULADONG] 1.概述（1）

骑猪看日落/ 2023年10月07日 22:37/ 0 赞/ 5 阅读

相关前缀和差分数组编程题集合

> 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。 > > 示例 1： > > 输入：nums = \[1,1,1\

太过爱你忘了你带给我的痛/ 2023年09月25日 22:08/ 0 赞/ 11 阅读

相关差分数组

文章目录差分数组 1.问题背景 2.解决方案 3.差分构造 4.应用差分数组 1.问题背景

清疚/ 2022年12月25日 06:57/ 0 赞/ 148 阅读

相关树状数组的变形（差分+数组数组）

暴力求解是不行的注意到差分后的一些性质 1 , 6 , 8 , 5 , 10 \{1,6,8,5,10\} 1,6,8,5,10，对应差分数组 1 , 5 , 2 ,

ゝ一世哀愁。/ 2022年10月11日 00:44/ 0 赞/ 120 阅读

相关 HDU 1541 Stars（树状数组）

> Stars Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others

不念不忘少年蓝@/ 2022年06月16日 04:49/ 0 赞/ 127 阅读

相关差分数组

先来看一道例题，给定一个长度为n(n≤107)的数列\{a1,a2,…,an\}，初始状态为0，m(m≤107)次操作，每次可以选择一个区间\[l,r\]，使下标在这个区间内的

小咪咪/ 2021年12月24日 15:23/ 0 赞/ 183 阅读

相关数据结构之差分数组

2019-06-25 推荐博客阅读：[https://www.sohu.com/a/271430685\_100201031][https_www.sohu.com_a_27

太过爱你忘了你带给我的痛/ 2021年12月15日 04:09/ 0 赞/ 189 阅读

相关 24. 树状数组1

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

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