解题思路：
分析问题，最直观的办法是暴力，但是在数据量1E5的情况下时间复杂度是达不到要求的。
引入差分数组，降低时间复杂度，对于a1,...,ana_1,...,a_na1,...,an构造差分数组cf1,...,cfncf_1,...,cf_ncf1,...,cfn对于cfi=a
展开全文
【模板】差分
难度：2星
差分模板题。如果每次操作都是 O(n)O(n)O(n) 复杂度进行模拟的话，肯定会超时。
我们观察到，对于一个数组，如果让 a[l]a[l]a[l] 加 kkk ，a[r+1]a[r+1]a[r+1] 减 kkk ，做一个前缀和之后，相当于 [l,r][l,r][l,r]
展开全文
利用差分数组 diff 减少区间操作的时间复杂度, diff 生成如下:
diff[0] = data[0]
for i in range(1, len(data)):
# 后一个元素与前一个元素相减
diff[i] = data[i] - data[i - 1]
之后可根据 di
展开全文
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define LCHILD(p) (((p) << 1) | 1)
#define RCHILD(P) (((p) + 1) <<
展开全文
（挣牛币用的）先开差分数组，再这样那样，最后求出差分数组的前缀和就好了
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, m;
cin &g
展开全文
#include <bits/stdc++.h>
using namespace std;
//差分数组
using ll=long long;
int main() {
int n,m;
cin>>n>>m;
vector<ll&g
展开全文
看了一下榜一的操作，感觉很棒
把原本的数据a和变化数据k做成两个数组a[]和，aa[]然后对变化数据k处理：
for(int i = 1; i <= m ;i++){
cin >> l >> r >> k;
aa[l]+=k;
展开全文
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include &l
展开全文
题意整理。
给定一个长度为n的正整数数组，对这个数组进行m次操作，每次操作给定左右边界l、r，以及一个参数k，将数组中下标在l到r范围内所有数加上k。
求k次操作之后的数组。
方法一（差分数组）
1.解题思路
首先定义一个差分数组，在每次操作中，标记对应增量的边界。
在操作完成之后，遍历差分数
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
