当前位置:网站首页>AcWing 242. A simple integer problem (tree array + difference)
AcWing 242. A simple integer problem (tree array + difference)
2022-07-06 11:17:00 【Jacob* ̄▽ ̄*】
Pre knowledge :
Tree array 、 Prefix sum and difference .
The question :
Ideas :
The instructions of this question are “ The interval increases ”,“ Single point query ”.
These two instructions are Naked difference What can be accomplished , The former O(1)
, the latter O(n)
, But according to the title , Element number n
And the number of inquiries m
The data range of is 1e5
, If you use naked difference , complete m
Single point query requires O(n^2)
, Obviously illegal , We should abandon .
The correct approach : Tree array + Difference , Or say Use the difference group to build a tree array .
The basic instruction of tree array is :“ Single point increase ”,“ Interval query ”, When combined with differential array, it can be realized “ The interval increases ”,“ Single point query ” 了 !
( Single point increase of the difference array , Corresponding to the original array interval increase , Before the differential array query i
Item prefix and corresponding original array query a[i]
)
Time complexity :
O(mlogn)
Code :
/* Save the difference group into the tree array , The original array is the prefix of the tree array and , Turn the problem into a tree array ,
Original array No x The number is the tree array 1~x And */
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n, m;
int a[N], c[N];
int lowbit(int x) {return x & (-x);}
int ask(int x){
int ans = 0;
while(x) {ans+=c[x], x-=lowbit(x);}
return ans;
}
void add(int x, int y)
{
for(; x<=n; x+=lowbit(x)) c[x]+=y;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
add(i, a[i]-a[i-1]);// use add Construct a differential tree array
}
while(m--)
{
char op[2];
int l, r, d, x;
scanf("%s",op);
if(*op=='C') {
scanf("%lld%lld%lld", &l, &r, &d);
add(l, d), add(r+1, -d);// use O(1) The complexity of interval modification
}
else{
scanf("%lld", &x);
printf("%lld\n", ask(x));
}
}
return 0;
}
边栏推荐
- Install MySQL for Ubuntu 20.04
- AcWing 1294.樱花 题解
- Did you forget to register or load this tag 报错解决方法
- 01 project demand analysis (ordering system)
- CSDN question and answer tag skill tree (I) -- Construction of basic framework
- La table d'exportation Navicat génère un fichier PDM
- MySQL master-slave replication, read-write separation
- Ansible practical series I_ introduction
- 02 staff information management after the actual project
- MySQL的一些随笔记录
猜你喜欢
Pytorch基础
Deoldify项目问题——OMP:Error#15:Initializing libiomp5md.dll,but found libiomp5md.dll already initialized.
Some problems in the development of unity3d upgraded 2020 VR
Leetcode 461 Hamming distance
Introduction and use of automatic machine learning framework (flaml, H2O)
一键提取pdf中的表格
基于apache-jena的知识问答
机器学习笔记-Week02-卷积神经网络
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
Did you forget to register or load this tag
随机推荐
Tcp/ip protocol (UDP)
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
LeetCode #461 汉明距离
Remember the interview algorithm of a company: find the number of times a number appears in an ordered array
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
Record a problem of raspberry pie DNS resolution failure
Copie maître - esclave MySQL, séparation lecture - écriture
Ansible practical Series II_ Getting started with Playbook
02-项目实战之后台员工信息管理
Did you forget to register or load this tag 报错解决方法
Knowledge Q & A based on Apache Jena
[number theory] divisor
Deoldify项目问题——OMP:Error#15:Initializing libiomp5md.dll,but found libiomp5md.dll already initialized.
Django运行报错:Error loading MySQLdb module解决方法
Installation and use of MySQL under MySQL 19 Linux
Project practice - background employee information management (add, delete, modify, check, login and exit)
neo4j安装教程
Asp access Shaoxing tourism graduation design website
Software testing - interview question sharing
Ansible实战系列二 _ Playbook入门