An example of a tree array in C language

An example of an C tree array

Recently learned the tree array, give me the feeling is this data structure good magic ah ^_^

Firstly, her constant is smaller than the line segment tree, and secondly, her implementation complexity is much lower than the line segment tree.

So it is necessary to master her.

The basic knowledge and principles of tree array 1 search 1 a lot on the Internet, I will not talk about, talk about some tree array application

1. Single point modification, and interval sum

#define lowbit(x) (x&-x) //  set  x  The number of zeros at the end of  y ,  the  lowbit(x) == 2^y 
void Update(int i,int v) //  Initialization with a single point of modification  
{
  while(i <= n)
  {
    c[i] += v ;
    i += lowbit(i) ;
  }
}

inline int Sum(int i)  //  Range sum  
{
  int res = 0 ;
  while(i > 0)
  {
    res += c[i] ;
    i -= lowbit(i) ;
  }
  return res ;
}

2. Interval modification and single point query

This is where the idea of difference comes in

Create a differential array c[], so that c[i] = a[i] - a[i-1] (a[i] represents the original number of i)

Then a[i] = (a[i] -i-1]) + (a[i-1] -a [i-2]) +... + (a[2] - a[1]) +a[1]

= c[i] + c[i-1] + ...... + c[2] + c[1]

So a single point query becomes an interval sum

So what about interval modification?

Let's look at an example like this:

a 1 3 4 5 7 10

c 1 2 1 1 2 3

If we add 2 to the interval [2,4], then

a 1 5 6 7 9 10

c 1 4 1 1 2 1

We can find that only the values of c[2] and c[5] have changed. In fact, the principle is very interesting. The difference between the elements before and after the interval is unchanged, and only (the difference between the first element of the interval and the previous one) and (the difference between the first element after the interval and the element at the end of the interval) has changed. So the interval modification problem becomes a single point modification problem.

  for(int i=1;i<=n;i++)
  {
    a[i] = read() ;
    Update(i,a[i]-a[i-1]);
  } 
/*  int x=0,y=0;    //  The ones that are commented out are spatial optimizations (beginners recommend skipping them first) 
  for(int i=1;i<=n;i++)
  {
    if(i%2)
    {
      x = read() ;
      Update(i,x-y);
    }
    else
    {
      y = read() ;
      Update(i,y-x) ;
    }
  } */
  int ii ;
  int k,x,y;
  for(int i=1;i<=m;i++)
  {
    ii = read() ;
    if(ii == 1)
    {
      x = read() ; y = read() ; k = read() ;
      Update(x,k);
      Update(y+1,-k);
    }
    if(ii == 2)
    {
      x = read() ;
      printf("%d\n",Sum(x));
    }
  }

(there are corresponding template questions P3374 and P3368 in luogu)

These are the two most basic applications of tree array, which will be updated after further study.

If you have any questions, please leave a message or come to the site community to exchange discussion, thank you for reading, hope to help you, thank you for your support of the site!