Title Description:

Title portal

Problem solving ideas:

First, we ignore the title of the topic (tree array template), and let's try a new algorithm - blocking.

• Block thought

Blocking is a beautiful violence (by DFT). His core idea is to maintain an interval (length: n n n) Divided into two poor people n \sqrt n n Sub interval to maintain separately. The length of each sub interval is n \sqrt n n , integrate the information of each sub interval covered by the interval we want to query, that is, the information of the interval we want to query.

What's the advantage of dividing the interval into blocks in this way? Because it can spread the maintenance complexity of an interval equally to each interval with a length of n \sqrt n n This will make the overall complexity better than the original violence, because it can divide the time of modification and query equally into Θ ( n ) \Theta (\sqrt n) Θ(n ​).

• Construction of block interval

It is not difficult to think in the construction of block intervals. We can explain and understand them directly in the comments in the code.

int S,C=0,belong[500010],st[10010],en[10010],sum[10010]={0};

S Represents the length of each sub interval, which is the root sign n Rounding.
C It represents the number of sub intervals divided by a large interval, which is generally also a root sign n Rounding
belong[i]Represents the second in the original interval i The number of the subinterval to which the elements belong
st[i] Represents the second i The left endpoint of a block, similarly en[i] Represents the right endpoint
sum[i] Representative section i The integration of the information of the first block element is represented here i The sum of all elements in the block.

inline void build()
{
   S=int(sqrt(double(n)));  //Find the size of S
   for(register int i=1;i<=n;i+=S)  //Set left and right endpoints for each block
   {
      st[++C]=i;
      en[C]=min(n,i+S-1);
   }
   for(register int i=1;i<=C;++i)  //Enumerate all blocks
   {
     for(register int j=st[i];j<=en[i];++j)  //Traverse the elements in each block and record the number of the block to which they belong
     {
       belong[j]=i;  //Indicates that the j-th element is the of the i-th block
       sum[i]+=a[j];  //Count the sum of the i-th element
     }
   }
   return ;
}

• Block interval single point modification

Obviously, only the block of this element will be affected by a single point of modification, so it's good to modify it directly.

inline void single(int x,int k)  In the first x Two positions plus k
{
  a[x]+=k;
  sum[belong[x]]+=k;   //Modify in the sum array of the information set of the block to which x belongs
  return ;
}

• Interval modification of block interval

We use an array d e l t a delta delta ， d e l t a i delta_i Delta record No i i The change of the whole block of i block will be changed only if and only if the block is completely and uniformly modified d e l t a delta delta.

Set the left end point of the interval to be modified as x x x. The right endpoint is y y y. So if x , y x,y x. Y just forms a block that has been divided previously:

-------][-------][---block---][-------][-------][-------
                    [x-------y]

That is to say, there is a third party i i i blocks make s t i = x   &   e n i = y st_i=x~\&~en_i=y sti = x & eni = y, then change directly d e l t a i delta_i The value of delta is sufficient.

  int l=belong[x],r=belong[y];
  if(l==r&&st[l]==x&&en[l]==y)
  {
    delta[l]+=k;  //Record the change of the 1st b l ock.
    return ;
  }

But if x , y x,y x. Y is not ideally just in one block, but contains an incomplete block at the same time?

-------][-------][-------][-------][-------][-------
               [x------------------y]

Very simple, for x , y x,y x. In the Y interval, we change the complete blocks d e l t a delta delta to change, while those incomplete blocks, we modify through a single point s i n g l e single single to change their original values one by one.

  for(register int i=x;i<=en[l];++i)  //Change the incomplete interval on the left
    single(i,k);
  for(register int i=st[r];i<=y;++i)  //Change the incomplete interval on the right
    single(i,k);
  for(register int i=l+1;i<r;++i)  //Unified modification of complete interval
    delta[i]+=k;

Therefore, a complete interval modification function r a n g e range range came out

int delta[10010]={0};
inline void range(int x,int y,int k)
{
  int l=belong[x],r=belong[y];
  if(l==r&&st[l]==x&&en[l]==y)
  {
    delta[l]+=k;
    return ;
  }
  for(register int i=x;i<=en[l];++i)
    single(i,k);
  for(register int i=st[r];i<=y;++i)
    single(i,k);
  for(register int i=l+1;i<r;++i)
    delta[i]+=k;
  return ;
}

• Partitioned interval query

Still consider querying one x , y x,y x. The interval of Y, if x , y x,y x. If y is in the same block, this may be the case:

-------][-------][-------][-------][-------][-------
                      [x-y]

At this point, x , y x,y x. Y is indeed in a block, but it is not completely contained in this block. In this case, we need special judgment

  int l=belong[x],r=belong[y],ans=0;
  if(l==r)
  {
    for(register int i=x;i<=y;++i)
      ans+=a[i]+delta[belong[i]];  //The simplest way to sum the interval is to use the delta array.
    return ans;
  }

As for the rest, we can still try to think like interval modification, which is divided into three parts: incomplete block on the left, complete block in the middle and incomplete block on the right. At the beginning, we integrated the information of the block, and the functions of the sum array and the delta array of change records were reflected. They greatly optimized the processing of the whole block.

  for(register int i=x;i<=en[l];++i)  //Left half
    ans+=a[i]+delta[belong[i]];
  for(register int i=st[r];i<=y;++i)  //Right half
    ans+=a[i]+delta[belong[i]];
  for(register int i=l+1;i<r;++i)  //Complete blocks can be accumulated directly by sum and delta card speed
    ans+=sum[i]+delta[i]*(en[i]-st[i]+1);

This is a complete block interval query function:

inline int query(int x,int y)
{
  int l=belong[x],r=belong[y],ans=0;
  if(l==r)
  {
    for(register int i=x;i<=y;++i)
      ans+=a[i]+delta[belong[i]];
    return ans;
  }
  for(register int i=x;i<=en[l];++i)
    ans+=a[i]+delta[belong[i]];
  for(register int i=st[r];i<=y;++i)
    ans+=a[i]+delta[belong[i]];
  for(register int i=l+1;i<r;++i)
    ans+=sum[i]+delta[i]*(en[i]-st[i]+1);
  return ans;
}

• Block essential card skills

Because the search and modification operations of blocks are approximate Θ ( n ) \Theta (\sqrt n) Θ(n ) so for this topic Θ ( m n ) \Theta (m\sqrt n) Θ(mn ) is Θ ( 500000 ∗ 500000 ) \Theta (500000*\sqrt{500000}) Θ(500000∗500000 ) a little hanging, so we should learn a kind of violence aesthetics as beautiful as segmentation - kachang.

• Turn off I / O synchronization flow
  I don't know why it's fast, but as long as you type these three lines, it will be much faster.

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

• Make function inline
  The actual operation is to add an inline before each function name.

inline void build()

• Unknown register
  Adding a register before the definition of cyclic variables will also speed up

for(register int i=1;i<=n;i+=S)

• Mysterious + + i
  Try to replace the accumulated i + + of all loops with + + i, so that you can get constant as much as possible?!

for(register int i=1;i<=C;++i)

In this way, we can card the realization of 1000ms and thrill AC with the help of C++14 compiler!

More outrageous card skills and strange things such as cyclic expansion and the use of cache nature are not mentioned here.

CODE:

#include <iostream>
#include <cmath>
using namespace std;
int n,m,a[500010],pos,b,c;
int S,C=0,belong[500010],st[10010],en[10010],sum[10010]={0};
inline void build()
{
   S=int(sqrt(double(n)));
   for(register int i=1;i<=n;i+=S)
   {
      st[++C]=i;
      en[C]=min(n,i+S-1);
   }
   for(register int i=1;i<=C;++i)
   {
     for(register int j=st[i];j<=en[i];++j)
     {
       belong[j]=i;
       sum[i]+=a[j];
     }
   }
   return ;
}
inline void single(int x,int k)
{
  a[x]+=k;
  sum[belong[x]]+=k;
  return ;
}
int delta[10010]={0};
inline void range(int x,int y,int k)
{
  int l=belong[x],r=belong[y];
  if(l==r&&st[l]==x&&en[l]==y)
  {
    delta[l]+=k;
    return ;
  }
  for(register int i=x;i<=en[l];++i)
    single(i,k);
  for(register int i=st[r];i<=y;++i)
    single(i,k);
  for(register int i=l+1;i<r;++i)
    delta[i]+=k;
  return ;
}
inline int query(int x,int y)
{
  int l=belong[x],r=belong[y],ans=0;
  if(l==r)
  {
    for(register int i=x;i<=y;++i)
      ans+=a[i]+delta[belong[i]];
    return ans;
  }
  for(register int i=x;i<=en[l];++i)
    ans+=a[i]+delta[belong[i]];
  for(register int i=st[r];i<=y;++i)
    ans+=a[i]+delta[belong[i]];
  for(register int i=l+1;i<r;++i)
    ans+=sum[i]+delta[i]*(en[i]-st[i]+1);
  return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(register int i=1;i<=n;++i) cin>>a[i];
    build();
    int d;
    for(register int i=1;i<=m;++i)
    {
      cin>>pos;
      if(pos==1)
      {
        cin>>b>>c>>d;
        range(b,c,d);
      }
      else
      {
        cin>>c;
        cout<<query(c,c)<<endl;
      }
    }
    return 0;
}