当前位置:网站首页>AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
2022-07-06 03:51:00 【Jacob* ̄▽ ̄*】
The question :
This problem requires the use of tree array Interval modification and Interval query .
Ideas :
stay Last question in , We maintain an original array with a tree array a The differential array of b, For every instruction “C l r d
”, hold b[i]
add d
, And then b[r+1]
subtract d
.
What has been discussed is :b
Of 1~x
The prefix and b[1~x]
After these instructions ,a[x]
Increased value .
that a
The prefix and of the sequence a[1~x]
The overall value added is
The above formula can be further rewritten into :
Derivation process :
Therefore, in this problem, we can consider adding a tree array , For maintenance i*b[i]
And , The above formula can be calculated directly .
To be specific , We build two tree arrays , Respectively c1
, c2
, Initially, all values are 0
, For every instruction “C l r d
”, Perform four operations :
- ①
c1
Ofl
Position plusd
. - ②
c1
Ofr+1
Position subtractiond
. - ③
c2
Ofl
Position plusl*d
. - ④
c2
Ofr+1
Position subtraction(r+1)*d
.
For every instruction “Q l r
”, We can directly apply the formula derived above to calculate .
This problem brings us a kind of thought , Separate items that contain multiple variables , Make different variables in the formula independent of each other , This idea is very important .
Time complexity :
O(mlogn)
Code :
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n, m;
int a[N], c1[N], c2[N];
int read() {// Fast reading
int x=0,f=1; char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
}
inline int lowbit(int x) {return x & (-x);}
int ask(int c[], int x)
{
int ans = 0;
while(x) {ans+=c[x], x-=lowbit(x);}
return ans;
}
int add(int x, int y, int c[])
{
for(; x<=n; x+=lowbit(x)) c[x]+=y;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
a[i] = read();
add(i, a[i]-a[i-1], c1), add(i, i*(a[i]-a[i-1]), c2);
}
while(m--)
{
char op[2];
int l, r, d;
scanf("%s", op);
l = read(), r = read();
if(*op=='C')
{
d = read();
add(l, d, c1), add(l, l*d, c2);
add(r+1, -d, c1), add(r+1, -(r+1)*d, c2);
}
else
{
printf("%lld\n", (r+1)*(ask(c1, r)) - ask(c2, r) - l*(ask(c1, l-1)) + ask(c2, l-1));
}
}
return 0;
}
边栏推荐
- Mathematical modeling regression analysis relationship between variables
- SSTI template injection explanation and real problem practice
- 施努卡:3d视觉检测应用行业 机器视觉3d检测
- STC8H开发(十二): I2C驱动AT24C08,AT24C32系列EEPROM存储
- [analysis of variance] single factor analysis and multi factor analysis
- Remote Sensing Image Super-resolution and Object Detection: Benchmark and State of the Art
- JVM的手术刀式剖析——一文带你窥探JVM的秘密
- 2.1 rtthread pin设备详解
- Pytoch foundation - (1) initialization of tensors
- KS008基于SSM的新闻发布系统
猜你喜欢
Suggestions for new engineer team members
Blue Bridge Cup - Castle formula
在 .NET 6 中使用 Startup.cs 更简洁的方法
C#(二十八)之C#鼠标事件、键盘事件
在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
【可调延时网络】基于FPGA的可调延时网络系统verilog开发
BUAA calculator (expression calculation - expression tree implementation)
2、GPIO相关操作
Serial port-rs232-rs485-ttl
Remote Sensing Image Super-resolution and Object Detection: Benchmark and State of the Art
随机推荐
如何修改表中的字段约束条件(类型,default, null等)
2.1 rtthread pin设备详解
Blue style mall website footer code
简易博客系统
Pointer written test questions ~ approaching Dachang
An article will give you a comprehensive understanding of the internal and external components of "computer"
2.1 rtthread pin device details
Canvas cut blocks game code
Pytoch foundation - (2) mathematical operation of tensor
Cf464e the classic problem [shortest path, chairman tree]
Hashcode and equals
ESP32(基于Arduino)连接EMQX的Mqtt服务器上传信息与命令控制
3.1 rtthread 串口设备(V1)详解
Microkernel structure understanding
C#(二十九)之C#listBox checkedlistbox imagelist
Scalpel like analysis of JVM -- this article takes you to peek into the secrets of JVM
C#(三十一)之自定义事件
RT-Thread--Lwip之FTP(2)
Edcircles: a real time circle detector with a false detection control translation
SAP ALV cell level set color