Data Structure 1 - Talk about tree-like arrays
Table of contents
Part1. Problems that tree-like arrays can solve
Part3. First knowing tree-like arrays
Part4. Properties of tree-like arrays
Part5. Tree-like array and interval query
Part6. Tree-shaped array and single-point modification
Part7. Tree-like array and tree building
Part8. Tree-like array and reverse order pairs
Part9. Weight tree array and dynamic k-th small
Part01: Problems that tree-like arrays can solve
Tree-shaped arrays can solve interval modification single-point query, single-point modification interval query, dynamic\(k\)Small numbers, reverse order peer problem.
Sometimes, with the help of differential arrays and auxiliary arrays, tree arrays can also solve the problem of stronger interval plus single point values and interval plus interval plus interval sum.
A problem that a tree-like array can solve, and a line segment tree can definitely solve it. However, the problem that line segment trees can solve is not necessarily solved by tree-like arrays.
However, among the problems that line segment trees and tree-like arrays can solve together, tree-like arrays are more efficient and have smaller code volumes.Save some time during competition and time spent on evaluation。
Therefore, tree-shaped arrays also have certain value and are worth learning from.
(The segment tree is the content of data structure 2)
Part02:lowbit
A long time agoWe have learned binary. We know,\(\text{lowbit}(x)\), the binary number of a number from behind to front is the first one\(1\)And the right one\(0\)The binary number formed (e.g.\((1000000000)_2\)) represents the decimal value.
That\(\text{lowbit}\)How can I find it simple?
Set a binary number\(x\)The lowest position\(1\)Yes\(k\)bit, then its\(0\to k-1\)All\(0\)。
Then at this time,\(-x\),Right now\(\text{~}x+1\), that is\(x\)Reverse again\(+1\), will\(k+1\)All are reversed to the highest position, but because\(0\to k-1\)All\(0\), after reverse, all become\(1\), and then due to\(+1\), and all became\(0\), carry to the first\(k\)and the\(k\)The bit is reversed and changed to\(0\), plus carry\(1\)Just turned into\(1\), once doing and operation with the original number, you can\(k+1\)All the positions are eliminated when they reach the highest position, and only the rest\(0\to k\)position, i.e.\(\text{lowbit(x)}\)Now.
so\(\text{lowbit(x)}=x\text{&}-x\)。
accomplish:
int lowbit(int a)
{
return a&(-a);
}
Part03: First knowing tree-like array
A long time ago,We have learned prefix and. It allows us to quickly get the sum of an interval. But preprocessing it is too slow, and once it is a dynamic array, the efficiency of the prefix sum will drop sharply. At this time, the tree-like array appeared.
We can assume that we need to ask\(a_1\)arrive\(a_7\)and. If we use the prefix and we can only use it\(a_1+a_2+a_3+a_4+a_5+a_6+a_7\). However, if there are three variables\(A=a_1+a_2+a_3+a_4,B=a_5+a_6,C=a_7\),So,\(a_1\)arrive\(a_7\)The sum becomes\(A+B+C\), very convenient.
We split a prefix into less than\(\log n\)The interval, then\(\log n\)The information (sum, product, etc.) of the segment interval becomes known.
Then how to ask for this\(\log n\)Where is the interval?
We can find that in this tree-like array,\(c_1\)The jurisdiction is\(a_1\)，\(c_2\)The jurisdiction is\(c_1\)and\(c_2\)，\(c_3\)The jurisdiction is\(a_3\)，\(c_4\)The jurisdiction is\(c_2,c_3\)and\(a_4\)…
At this time, when we want to calculate\(a_1\)arrive\(a_7\)The sum can be followed as follows:
See first\(c_7\),Discover\(c_7\)Under the jurisdiction\(a_7\), and then look\(c_{7-1=6}\),Discover\(c_6\)Under the jurisdiction\(a_5,a_6\), and then look\(c_{5-1=4}\),Discover\(c_4\)Under the jurisdiction\(a_1,a_2,a_3,a_4\), and then look\(c_{1-1=0}\),Discover\(c_0\)If it does not exist, the step ends.
The three numbers we've seen\(c_7,c_6,c_4\)Added up\(a_1\)arrive\(a_7\)and.
Part04: Properties of tree-like arrays
Tree-like arrays have the following properties:
1.Each\(c\)The elements of the array all govern the sum of the elements in the subtree rooted with it.
2. The father node of each node is (set the subscript as\(x\)And remove the root node)\(x+\text{lowbit(x)}\)。
3.\(\text{lowbit(x)}\)That is\(x\)The number of leaf nodes of the subtree of the root.
Part05: Tree-shaped array and interval query
According to the properties of tree array\(3\), let's check\(a_1\)arrive\(a_x\)The answer can be added continuously\(c_x\), then\(x-\text{lowbit}(x)\)until\(x=0\)Come to get the answer.
accomplish:
int ret(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
Part06: Tree-shaped array and single-point modification
Questions that require tree arrays are generally dynamic, and we need to modify them at this time.
According to the properties of tree array\(2\), when we place a number (suppose its subscript is\(x\)) Plus\(y\)When we need to\(c_x\)All father nodes are added\(y\), this is a single point of modification.
accomplish:
void add(int x,int y)
{
while(x<=n)
{
c[x]+=y;
x+=lowbit(x);
}
}
reduce\(y\)take\(y\)remove\(y\)All can be solved, and it is a universal magic weapon.
Part07: Tree-like array and tree building
Beginners with tree-like arrays, we can use time complexity\(O(n\log n)\)the creation algorithm.
In fact, it can be transformed into\(n\)Single point modification.
That is, for a subscript\(i\)Number of\(a_i\), using single point of modification\(\text{add}\)function,\(\text{add}(i,a_i)\)You can make achievements.
accomplish:
void build(int l,int r)
{
for(int i=l;i<=r;i++)
{
add(i,a[i]);
}
}
Part08: Tree-like array and reverse order pair
How to use tree arrays to find in reverse order?
Yes, for\(1\)arrive\(n\), please\(1\to a_i\)The sum of the answer is added to this value, and modify it alone\(i\)(plus\(a_i\)）。
Part09: Weight tree array and dynamic k-th small
With the weight segment tree (data structure 2 content) available, how can there be no weight tree-like array?
They are generally used to solve the smallest problem.
So how to do it?
Consider doubling (7 details of improving the group algorithm).
set up\(x=0\)，\(sum=0\),enumerate\(i\)from\(\log_2n\)Down to\(0\)：
- Query the weights in the array\(x+1\to x+2^i\)The interval and\(t\)。
- if\(sum+t<k\), successfully expanded,\(x=x+2^i\)，\(sum=sum+t\); Otherwise, the extension fails and no operation is performed.
This is obtained\(x\)satisfy\(1\to x\)Prefix and\(<k\)the maximum value, so the final\(x+1\)That's the answer.
Of course, it can also be solved by searching and collecting.
Code:
int slove(int k)
{
int sum=0,x=0;
for(int i=log2(n);i>=0;--i)
{
x+=1<<i;
if(x>= n||sum+t[x]>=k)
{
x-=1<<i;
}
else
{
sum+=t[x];
}
}
return x+1;
}
At this point, data structure 1 ends.