[AcWing algorithm improvement course] high order data structure tree array (C + + problem solution) (to be supplemented)

catalogue

Function of tree array

(1) Classic template of tree array

(2) About memory templates

Loulan Totem

I can't prove math, but I can learn and use it. Do you know the pain of y always talking about proof for an hour

Function of tree array

  1. Single point increase (time complexity is O (logN))
  2. Interval query prefix and (time complexity is O (logN))
  3. Reverse order pair (but not as good as merge sort)
  4. Extension: difference + formula

Compared with the original array a[N], the increased time complexity of a single point is O(1), but the time complexity of interval query and is O(N)

Compared with prefix and array pre[N], the time complexity of interval query sum is O(1), but the complexity of single point increase is O(N)

Therefore, we chose a compromise, that is to make both operations log n complexity

(1) Classic template of tree array

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
int a[N];
int tr[N];
int n;//point

int lowbit(int x)
{
    return x & -x;
}

void add(int x,int c)//Add the constant c to the position of x
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x)//Find the prefix sum before the x position
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(1)
    {
        cout<<"First query prefix and(1)"<<endl;
        for(int i=1;i<=n;i++) cout<<sum(i)<<" ";
        cout<<endl;
        for(int i=1;i<=n;i++) add(i,1);//Add 1 to each position

        cout<<"Each location is prefixed with 1 for the second query(2)"<<endl;
        for(int i=1;i<=n;i++) cout<<sum(i)<<" ";//Prefix and
        cout<<endl;
        cout<<"Query the value size of each point(3)"<<endl;
        for(int i=1;i<=n;i++) cout<<sum(i)-sum(i-1)<<" ";//Query the value of a single point
        cout<<endl;
        break;
    }
    system("pause");

    return 0;
}

(2) About memory templates

  1. First, remember this picture
  2. For the add function, because the tree array maintains the prefix and sum of a part of the tree, it can only affect the tree array at this position and behind it. Because the latter tree array needs to be updated, it should be updated backward in the unit of lowbit(i)
  3. For sum function, because the tree array maintains the prefix and sum of some trees, it queries forward. The size of each section is lowbit(i). Use res variable to record the cumulative sum of each section of tree array and return it
  4. If you don't understand, write more times, or go back and see the proof = -=

Loulan Totem

241. Loulan Totem - AcWing question bank

Core idea:

  1. (multiplication principle) we can know that if we enumerate a point in the middle and count the number of conditions satisfied on the left and right sides, then the product result of the left and right sides is a result; For example, if we require the number of 'V' shaped points, we can preprocess the number of points on the left higher than the middle point and the number of points on the right higher than the middle point at position i, and then multiply it to count the enumerated point as the number of middle points
  2. Then the problem now is to quickly find the number of heights less than or greater than this point in an interval
  3. Note that at this time, because the target is the number of numbers, not the size of numbers, this inspires us that it is more reasonable for the value in a position to be the number of numbers; Well, for this position, the attention condition is < less than or greater than this number >, that is, the size of the number is actually used as a key, that is, an index
  4. The problem analysis here has a little outline. Please see the code + detailed notes for the next details
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=2000010;
typedef long long ll;
int n;
int a[N],t[N];//t[i] represents the coverage range and of node i of the tree array
//Lower[i] indicates the number of numbers on the left that are smaller than the i-th position
//Greater[i] indicates the number of the left side larger than the i-th position
int Lower[N],Greater[N];

//Returns the value of the nonnegative integer x composed of the lowest 1 and the following 0 in the binary representation
int lowbit(int x)
{
    return x&-x;
}

//Add k to the x-th number in the sequence
void add(int x,int k)//In the upper right, add k maintenance between the areas in the t array in the unit of lowbit(i)
{
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=k;
}

//Sum of the first x numbers of the query sequence
int ask(int x)//Query in lowbit(i) at the upper left
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=t[i];
    return sum;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    From left to right, count the left ratio of each position in turn i number y The number of small numbers and the number of large numbers
    for(int i=1;i<=n;i++)
    {
        int y=a[i];//Number i

        //All kinds of tree array have been added in front to count the number of occurrences of numbers in the interval [1,y-1]
        Lower[i]=ask(y-1);
        
        //Count the number of occurrences of the number in the interval [y+1,n] among all the numbers that have been added to the tree array
        Greater[i]=ask(n)-ask(y);
        
        take y Add a tree array, that is, numbers y 1 occurrence
        add(y,1);//Note that y here is a[i], that is, the size of the number, because it has been enumerated by location
        //Therefore, it is not necessary to consider the sequence of positions, but only the size relationship of numbers
    }

    //Clear the tree array, and count the number of numbers smaller than the i-th number y and the number of large numbers on the right of each position from right to left
    memset(t,0,sizeof t);

    ll resA=0,resV=0;
    //Statistics from right to left
    for(int i=n;i>=1;i--)
    {
        int y=a[i];

        resA+=(ll)Lower[i]*ask(y-1);//Total number of numbers of [1,y-1] queried to the right
        resV+=(ll)Greater[i]*(ask(n)-ask(y));//Total number of numbers of [y+1,n] queried to the right

        add(y,1);//Similarly
    }

    printf("%lld %lld\n",resV,resA);

    return 0;
}

I'm tired and can't think about it. I'll watch it again tomorrow

Tags: C++ Algorithm data structure linked list

Posted by maliary on Sat, 14 May 2022 23:30:16 +0300