Block —— Elegant violence

Preface ：

　　 First , Let's consider such a model ： There is a continuous sequence a[1]~a[n], Then now we need to perform several types of operations ：

The author ：  Find the sum of one of the intervals

Intelligence quotient (IQ) 180 A baby ： Oh dear , Why are you so stupid , Just record the prefix and number of this sequence directly ？

　　 Record a[1]~a[i] And for sum[i], Then there is obviously sum[i+1]=sum[i]+a[i+1], We demand a[l]~a[r] Just directly sum[r]-sum[l-1] Chant .

The author ： Interval plus a value

Because a baby is a big man , Two minutes later ： I know something called line segment tree ( A tree structure , It can maintain the excellent data structure of interval summation and single point modification )！！！

The author ： Query how many numbers there are in a section <k (k>0 And given )    

A baby ：

The author ： by the way , Forgot to tell you ,k It's different every time , also , Extremely much . in addition , To prevent loading * Don't let me write a balanced tree ( Another excellent data structure that can do a lot of things )+ Line segment tree , The occupied space cannot exceed ****Mb

A baby :

---

Here's a rookie who can understand the algorithm ： Block

Block , seeing the name of a thing one thinks of its function , Is to divide a sequence into small pieces and deal with them , maintain .

We take a paragraph as a whole , Only record and maintain the relevant information of the whole , It's divided into blocks .

First , For the question mentioned in the preface , A very simple approach is ：

　　1. From the query interval l To r Sweep past , Add the swept value every time , namely ans=∑ri=la[i]ans=∑i=lra[i] 

　　2. Put... Directly a[i]a[i] Just reassign a[i]=newa[i];

　　3. From the query interval l To r Sweep past , Every time I meet <k The location of , answer +1

you 're right , It's silly, isn't it ？

however , Blocking is optimized on this basis ！！！

Suppose our total sequence length is n, Then we cut it into pieces n−−√n block , Then look at everything in each piece as a whole ,

Now explain a few terms used in this article ：

Complete block ： A block completely covered by an operation interval

Incomplete block ： Block with incomplete coverage of operation interval

Then let's see how to get the answer ：

　　1. For complete blocks , We want something that can directly find the sum of the whole block , therefore Each block should maintain the sum of all elements of the block .   

　　  . For incomplete blocks , Because there are few elements ( At most   total n /  Number of blocks = n−−√n  individual ) When n=1000000 There are at most 1000 individual , Compare the , We can directly sweep this small statistical answer ,

　　  . Tips ： If the length of the incomplete block is covered > Half the length of the block maintained , Why not use the sum of this block - What about the value of the element that has not been overwritten ？

　　2. here , Let's change our thinking , Record a lazy    Mark ( Why lazy, Because I'm lazy ), Indicates how much the whole block has been added ,

　　  . For complete blocks , We directly lazy+= Add the number of x, The sum in the block ans+=x* Element number ( Because every element is added x)

　　  . For incomplete blocks , Just modify it directly , By the way, you can put lazy The mark is clear .

　　3. Oh dear , This is a bit difficult ,

　　  . To find the number of elements less than one value in each complete block ,

　　   Obviously, we have to ask that the elements in the block are Orderly , So you can use two points ( An algorithm for fast query in an ordered sequence ), For intra block queries .

　　  . Incomplete block violence is good

　　  . In this case, you need to sort the elements in each block in advance .

　　  . If there is any modification , Because the whole block is added at the same time ( subtract ) a number , The relative size of each number will not change , But if it's an incomplete block, it will change , In this case , Or because the number of elements is small , Just rearrange it ?

 

then , This problem is finished in a seemingly tall way …… Isn't it much better than the silly violence before ？

In many places , We can apply the idea of segmentation , Gather parts into a whole , Maintain the value of each number into maintaining some overall values ,

A very common example is ： Why does the head teacher divide the class into groups ？ Because he doesn't want to receive homework or receipts one by one qwq Give it to the team leader, and then the team leader gives it to the teacher qwq

such , We don't have to look for it one by one qwq

Then we'll finish the basics .

A little advanced ：

Actually , Each piece can maintain more than the above-mentioned things , We can maintain the maximum common divisor of the current interval , What is the maximum XOR sum ……

Objectively speaking , Chunking can maintain a lot , Just figure out how to preprocess , How to maintain the modified model , When counting the answers, just add them up .

I hope that's helpful .

Copyright notice ： This article is reproduced in the blog Garden blogger , The purpose of reprint is to facilitate learning
Link to the original text ：https://www.cnblogs.com/arcturus/p/9302143.html