Acwing 241 Loulan totem (detailed explanation of tree array)

Tree array

Problem introduction

Tree array is a high-level data structure that is easy to implement .

We know , For an array a[i], Its prefix and s[i] Express a Before the array i The sum of the elements , And find the interval l To r The sum of the elements of can be expressed as s[r] - s[l-1] Come and ask for .

Now there is a single point of modification , The problem of interval query , That is, modify the original array a An element in , Then query the sum of elements in a certain interval .

Modification of violent practices a The time complexity of an element in is O（1）, The query interval and complexity are O（n）; If you use prefixes and arrays , The complexity of query interval and operation can be reduced to O（1）, But the complexity of updating the prefix and array after a single modification operation is O（n） Of .

Now we need to realize that the complexity of modification and query operations is O（logn） An algorithm of .

lowbit operation

Binary bit operation can be very simple to achieve some functions , such as x & (x - 1) It can be x The last binary representation of 1 Get rid of , and lowbit Operation can only keep the last of an integer 1,lowbit(x) = -x & x How to realize this function ？（ If you don't want to know the principle , You can skip the next three paragraphs , Lighten the burden of thinking .）

First , Binary code is divided into original code 、 Complements and inverses , The source code and complement of positive numbers 、 The reverse code is the same , The inverse code of a negative number is equal to the original code, except for the sign bit , The complement of a negative number is equal to the inverse of the original code by bits except for the sign bits and then add 1, What is stored in the computer is the complement of integers .

such as x = 0,1010, At the beginning 0 The sign bit ,-x The original code of is 1,1010, The inverse code is 1,0101, The complement is 1,0110,

that x & -x = 0,0010, And x Of 0,1010 Compared to the last one 1. A clearer explanation is to start x the last one 1 Followed by several 0, for instance 1000 Yes x The last one after bitwise inversion 1 Turned into 0, The following numbers are 1, That is to say 0111, Plus a 1 Will be carried in succession to become 1000, and x The initial appearance is consistent , and x The last 1 The previous elements are reversed with x Phase and nature have become 0. This keeps x The last 1.

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

Definition of tree array

Now we know lowbit(x) Can be extracted x The last 1, So how to implement single point modification and interval query operations within logarithmic time complexity ？ Let's first analyze why the complexity of single point modification using prefixes and arrays is O（n） Of ,s[i] Stored before i The sum of the elements , let me put it another way ,s[i] Managing the front i Elements , and a[i] Be behind n - i Elements manage . If we modify a[i], So from s[i] Until s[n] this n - i + 1 The prefix and of the elements have been changed , In the final analysis, it is because s[n] It stores n The sum of the elements , Once modified , Pull one hair and move the whole body . If we define a new prefix and array tr[n] To store n front logn The sum of the elements ？ So it's equivalent to tr[i] Only manage logi Elements , Only here logi One of the elements changed ,tr[i] Will change , The complexity of modification will be greatly reduced .

Now we define it tr[n] For the first time n Elements and their predecessors lowbit(n) - 1 The sum of the elements , such as n = 6 when ,6 = （0110）,lowbit（6） = （10） = 2,tr[6] = a[6] + a[5].

As shown in the figure , In the picture C Arrays are what we call tr Array , We will tr[i] Managed elements are treated as i The child node of , such as tr[6] Is to find the sum of the fifth and sixth elements , that tr[5] Namely tr[6] The child node of . Why? tr[i] To manage the front lowbit(i) An element ？ This is determined by binary grouping , such as 7 = 0111 = 0001 + 0010 + 0100 = 1 + 2 + 4, We divide the first seven elements into three groups , The first group 7, the second 6 5, The third group 4 3 2 1, It can be seen that , The number of each group happens to be lowbit Value ,lowbit(7) = 1, be left over 6 Elements ,lowbit(6) = 2, be left over 4 Elements ,lowbit(4) = 4. That is to say :

tr[7] = a[7]
tr[6] = a[6] + a[5]
tr[4] = a[4] + a[3] + a[2] + a[1]

We ask for the front 7 The sum of the elements s7 = tr[7] + tr[6] + tr[4], Seek before x The sum of the elements ,x Some of them 1,lowbit The operation will be performed several times , front x Each element is divided into groups , and x in 1 The number of must not exceed x The word is long , That is, the interval summation operation is at most right logn Sum elements , To achieve the sum of O(logn) Complexity .

What about the complexity of the modification operation ？ We know that for nodes x for , In front of the lowbit(x) - 1 All elements are x The child node of , Their changes will cause tr[x] Changes , So we modified x, For subscripts less than x In terms of the elements , It doesn't matter , because tr[i] Only the previous elements will be managed , modify x, The first change is a[x], And then it changed tr[x], And then along x The parent node of is up , Affect x The value of the ancestor node of , So how to ask x What about the parent node ？ That is, managing x The node of .

such as tr[12],12 = 1100,lowbit（12） = 4, That is to say 12 Manages the 12,11,10,9 Four nodes , For any of the child nodes, such as 10 = 1010 for lowbit(10) = 2,10 + 2 = 12,10 The parent node of is 12, Another example 9 = 1001,lowbit(9) = 1,9 + 1 = 10 in other words ,9 The parent of is 10.lowbit(9) = 1, therefore 9 Only manage yourself , then 10 Manages the 10,9,12 Manages the 12,11,10,9, After that is 16 Managing the front 16 Elements . We came to the conclusion that , node x The parent of is x + lowbit(x).

Implementation of tree array

If you don't want to understand the details , Only consider implementing , Only three things need to be understood ：

• lowbit(x) It means take x The last 1
• tr[x] Manages the x Ahead lowbit(x) Elements
• x The parent node in the tree array is x + lowbit(x)

Knowing these three points , Then we can insert and query the tree array .

Insert x, Will only affect x And its ancestor nodes , It is equivalent to updating from bottom to top tr Array

void add(int x,int c){
    
    for(;x <= n;x += lowbit(x)) tr[x] += c;
}

Before query x The sum of the elements , It is equivalent to giving x grouping , The first group is x To x - lowbit(x) + 1, The second group is x - lowbit(x) To x - lowbit(x) - lowbit(x - lowbit(x)) + 1,…. The sum of the first set of elements is tr[x], The sum of the second group of elements is tr[x-lowbit(x)],…. Adding up the elements of each group is the first x The sum of the elements .

int query(int x){
    
    int res = 0;
    for(;x;x -= lowbit(x)) res += tr[x];
    return res;
}

As for intervals and , Before finding out r Before the sum of the elements l - 1 The sum of the elements , Subtract and you get the sum of the intervals .

The core operation code of tree array is just a few lines , It's still very concise . Of course, this is just a single point update of the tree array , Application of interval summation , If the interval maximum value is required , Change the definition of the tree array , Can be defined as tr[i] by i And to the left lowbit(i) The highest value of the elements , It is also an element management lowbit Elements , Complexity and interval summation are consistent .

The application of tree array to find the number of reverse pairs

For example, there is an array 3 4 2 5 6 1, We ask how many pairs in reverse order there are in this array , For an element , You can traverse the following elements , Count the number of elements smaller than this element , You can find the number of pairs in reverse order . We can also use hash How many elements are larger than it in each element coordinate , Traversing 3,cnt[3] = 1, then cnt[4] = 1, Traversing 2 when , If all the elements in the array are within a certain range , So we can traverse cnt Array 2 The position after , Statistics show that at this time cnt[2] How many elements are there after , And then there was 2 Elements , therefore 2 There are two elements larger than it , This statistic shows how many elements are larger or smaller on the left of a number , Need to be right cnt Array sum , Because we need to update constantly in the process of traversal cnt Array , So it also belongs to single point update , Interval query problem , You can use a tree array to solve .

The initial conditions cnt[i] = 0,cnt The array is the original array ,tr[i] An array is cnt Array generated tree array . The original array cnt The values are all 0, Indicates that no element appears , Traversing 3, Tree array 3 The sum of the elements on the right is still 0, therefore 3 There is nothing on the left 3 Big elements , take 3 Insert into tree array , The original array cnt[3] = 1; Continue traversing 4,cnt In the array 4 The sum of the elements on the right is still 0, take 4 Add tree array ,cnt[4] = 1; Then go through 2, At this point, the tree array is smaller than 2 There are two big ones , It's done 2 The number of elements larger on the left .

The following question is the classical application of tree array in finding the number of pairs in reverse order .

Title Description

After completing the assigned task , In the west 314 Came to the west of Loulan ancient city .

It is said that a long time ago on this land ( Earlier than Loulan ancient city ) Two tribes live , A tribe worships sharp knives (V), A tribe worships shovel. (∧), They use them separately V and ∧ To represent the totems of their respective tribes .

In the west 314 A huge mural was found under the ancient city of Loulan , The mural is marked n A little bit , After measurement, it was found that n The horizontal and vertical positions of two points are different .

In the west 314 I think the information contained in this mural is different from this n The relative position of two points , Therefore, we might as well set the coordinates as (1,y1),(2,y2),…,(n,yn), among y1∼yn yes 1 To n An arrangement of .

In the west 314 I intend to study how many totems are contained in this mural .

If three points (i,yi),(j,yj),(k,yk) Satisfy 1≤i<j<k≤n And yi>yj,yj<yk, These three points constitute V Totems ;

If three points (i,yi),(j,yj),(k,yk) Satisfy 1≤i<j<k≤n And yi<yj,yj>yk, These three points constitute ∧ Totems ;

In the west 314 Want to know , this n The number of totems of two tribes in a point .

therefore , You need to write a program to find V The number of and ∧ The number of .

Input format
Number one on the first line n.

The second line is n Number , Represent the y1,y2,…,yn.

Output format
Two Numbers , Space separates the middle , In turn V The number of and ∧ The number of .

Data range
For all the data ,n≤200000, And the output answer will not exceed int64.
y1∼yn yes 1 To n An arrangement of .

sample input ：
5
1 5 3 2 4
sample output ：
3 4

analysis

Statistics V The number of pairs is the same as the method of statistical reverse order pairs , We can enumerate intermediate elements , Altogether n In this case , For example, the intermediate element is x, In the array x On the left a Ratio x Big elements ,a There is... On the right b Ratio x Big elements , So we can do that a To the left of the element larger than it , And then x To the right of the, select any element larger than it , It can form V It's structured , According to the principle of multiplication, there are ab Medium combination scheme . Additional requirements ∧ Number of , So what we need to count is the left side of each element 、 The number of elements larger and smaller on the right .

There is a good condition for this question “y1∼yn yes 1 To n An arrangement of ”, That's the guarantee y The values of are different and have rules to follow , We use the array array to find out the number i The number of elements smaller on the left of the element t1, and i To the left of the, there are i - 1 Elements , among t1 One is smaller than it , Then the rest i - 1 - t1 Every element is bigger than it .y There are... In the array n Elements , No more than n, More than yi The small elements are yi - 1 individual , Since the second time i There are... On the left of the elements t1 A smaller element , So the number of elements smaller than it on the right is t2 = yi - 1 - t1, Similarly, we can find that the larger element on the right is n - i - t2 individual . In this way, a query operation is performed to find the i The number of elements on the left and right sides that are larger and smaller than it .

Code

#include <cstdio>
using namespace std;
const int N = 200005;
typedef long long ll;
int a[N],tr[N];
int n;
int lowbit(int x){
    
    return -x & x;
}
void add(int x,int c){
    
    for(;x <= n;x += lowbit(x)) tr[x] += c;
}
int query(int x){
    
    int res = 0;
    for(;x;x -= lowbit(x)) res += tr[x];
    return res;
}
int main(){
    
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)   scanf("%d",&a[i]);
    ll res1 = 0,res2 = 0;
    for(int i = 1;i <= n;i++){
    
        ll t1 = query(a[i]-1),t2 = i - 1 - t1;
        res1 += t2 * (n - a[i] - t2);
        res2 += t1 * (a[i] - 1 - t1);
        add(a[i],1);
    }
    printf("%lld %lld\n",res1,res2);
    return 0;
}