preamble
The essence of many algorithms is statistics. Line trees are used for statistics and are a bridge between the original array and the prefix sum.
The Power of Statistics" Tsinghua University - Kunwei Zhang
About Line Tree
Prior knowledge:Line Tree OIWiki。
A line segment tree is a specializedMaintenance interval issuesThe data structure of the
The line segment tree performs the informationbinary processingand maintained on a tree structure as a way to get the processing speed up to\(O(\log{n})\) Level.
A Line Tree Implementation
Due to the tree structure characteristics of the line tree, each modification query can be bisected from the root node down to find the node that needs to be used, so the more common and fast line tree will use therecursive (calculation)Realization.
However, the recursive implementation of the line tree is not as easy to implement as it is to start from the root node each time therecursive (calculation)Passing down subtree information results in large constants that are prone to cardinality, hence the appearance of theRecursive implementations with smaller constantsof a line tree (worship the zkw bigwigs).
zkw Line Tree
Let's start with some small principles.
I. Principles
due torecursive (calculation)The implemented line segment tree is not a full binary tree with indeterminate leaf node positions, resulting in the need to start at the root node for each operationtop-down recursionFinding leaf nodes sequentially and maintaining them on backtracking, the recursive process constant is then larger.
So the zkw tree is a straightforward tree to build.full binary tree (math.), the original sequence information is maintained at the bottom.strictly regulateParent-child node relationship where subtrees of nodes at the same level are equal in size.
This way each leaf node can be found and modified directly, due to the binary tree parent-child node'sbinary relationwhich can then recursively find the father of the corresponding node directlybottom-upGround maintenance of node relationships.
II. Initialization
1. Tree-building
For the length of\(n\) sequence to build a zkw line segment tree with aat least\(n+2\) leaf nodeThe There are 2 of these that are used to help maintain interval informationimaginary pointYes\(n\) A node used to store the original sequence information.
As shown in the figure (Template] Line Tree 1(the sample example below):
Build the tree by first finding the imaginary point\(P\) position, and then just read in the information directly to the other leaf nodes: the
//first find the imaginary point P
P = 1;
while(P<=n+1) P<<=1; //node depth doubles the number of nodes in the current layer for each additional layer
for(int i=1;i<=n;++i) read(tr[P+i]);
2. Maintenance
According to the above, since the parent-child relationship is strictly determined, it is straightforward to do the initialization by traversing all the nodes bottom-up to maintain the parent-child relationship:
//push_up
for(int i=P-1;i;--i){//i=(P+n)>>1
tr[i] = tr[i<<1|1]+tr[i<<1];
tr[i] = min(tr[i<<1|1],tr[i<<1]);
tr[i] = max(tr[i<<1|1],tr[i<<1]);
//...
}
III. Introduction to the concept
1. Perpetuating lazy tagging
with the recursive line segment tree of\(lazy\) \(tag\) Unlike its downward recursion, it needs to first drop the markers and clear them to maintain the information.
However, in maintainingassociative law (xy)z = x(yz) (math.)zkw line segment tree when the operation of the\(lazy\) \(tag\) will onlytotalization, and will not be decentralized and emptied before modification and query.
2. "Sentinel" nodes
In interval operation, two sentinel nodes are introduced, on the left and right sides of the interval, theTurning closed intervals into open intervals for processing。
There are two chains from the two sentinel nodes to the root, and the nodes adjacent to and in the middle part of the two chains are all the nodes whose information is needed for this operation.
As in the figure (which follows the first one, the number's in the nodes are interval sums):
Example:Template] Line Tree 1The first operation\(query(2,4)\)：
Also, this explains why the tree is built with leaf nodes on the\(2\) An imaginary point (so as not to cross the line, of course).
(1) Why it is possible to determine which nodes need to be used
When operating, you only need to operate on the common ancestor of a single-element interval in the interval.
We have chosen two chains, the middle part of which contains exactly all the nodes related to the operative interval, and the nodes neighboring the two chains are clearly the common ancestors of all the intervals.
The operation only needs to manipulate the information on these nodes.
(2) How to determine which nodes to use during recursion
Observe the picture we just pushed out by hand and notice:
For the left sentry\(S\), whose sibling node is required when it is a left son;
For the right sentry\(T\), whose sibling nodes are needed when it is a right son.
After each operation\(S\) cap (a poem)\(T\) Walk up to your own father node and then maintain the paternity before proceeding to a new round of operations.
(coll.) fail (a student)\(S\) cap (a poem)\(T\) When they are brother nodes to each other (having traveled to the intersection of the two chains), they stop the operation and then maintain the information upwards to the root node.
IV. Queries and modifications based on the law of union
1. Interval modification
Take the interval plus as an example。
Similar to the recursive line tree operation, the update needs to know the current node'sSubtree size。
At each update, the value of the current node is increased by its marker times the subtree size; the value of its marker is simply accumulated normally.
Perpetuating lazy tagsReduced marking decentralizationBringing in constants.
//
inline void update_add(int l,int r,ll k){
l=P+l-1; r=P+r+1;// Sentry position
int siz = 1;// record current subtree size
while(l^1^r){// When l and r are brothers to each other, only the last bit is different
if(~l&1) tr[l^1]+=siz*k,sum[l^1]+=k;
if(r&1) tr[r^1]+=siz*k,sum[r^1]+=k;
// similar to recursive line tree tr[p] += tag[p]*(r-l+1)
l>>=1; r>>=1; siz<<=1;
// Double the size of the subtree each time you go up
tr[l] = tr[l<<1]+tr[l<<1|1]+sum[l]*siz;//maintain parent-child relationship
tr[r] = tr[r<<1]+tr[r<<1|1]+sum[r]*siz;
}
for(l>>=1,siz<<=1;l;l>>=1,siz<<=1) tr[l] = tr[l<<1]+tr[l<<1|1]+sum[l]*siz;//update upload to the root node
}
2、Interval search
Since the interval we need to query is divided into two parts by the left and right sentinels, but the two parts of the molecular tree are not necessarily equal in size.
So the sizes of the subtrees of the query interval contained in the nodes reached by the left and right sentinels are to be maintained separately.
//
inline ll query_sum(int l,int r){
l=l+P-1; r=r+P+1.
int sizl = 0,sizr = 0,siz = 0,siz = 0,siz = 0
int sizl = 0,sizr = 0,siz = 1;// maintain left and right subtree sizes respectively
while(l^1^r){
if(~l&1) res+=tr[l^1],sizl+=siz;//update answer and subtree size
if(r&1) res+=tr[r^1],sizr+=siz;
l>>=1; r>>=1; siz<<=1;
res += sum[l]*sizl+sum[r]*sizr;
// Even though the interval sum stored in the current node is not needed for use, since it is the father node of two sentinels and the tag will not be passed down
// so its tag will contribute to the answer, so the tag contribution needs to be added
}
for(l>>=1,sizl+=sizr;l;l>>=1) res+=sum[l]*sizl;//Accumulate to root node
return res;
}
If the maintenanceInterval MaximumDitto:
//
inline void update_add(int l,int r,ll k){
l=P+l-1; r=P+r+1.
while(l^1^r){
if(~l&1) sum[l^1]+=k,maxn[l^1]+=d;
if(r&1) sum[r^1]+=k,maxn[r^1]+=d;
l>>=1; r>>=1;
maxn[l] = max(maxn[l<<1],maxn[l<<1|1])+sum[l];
maxn[r] = max(maxn[r<<1],maxn[r<<1|1])+sum[r];
}
for(l>>=1;l;l>>=1) maxn[l]=max(maxn[l<<1],maxn[l<<1|1])+sum[l];//update upload to root node
}
inline ll query_max(int l,int r){
l=l+P-1; r=r+P+1;
ll resl = 0,resr = 0;//record the left and right side max values respectively
while(l^1^r){
if(~l&1) resl=max(resl,maxn[l^1]);
if(r&1) resr=max(resr,maxn[r^1]);
l>>=1; r>>=1;
resl += sum[l];// marker permanence, so accumulate marker values
resr += sum[r];
}
for(resl=max(resl,resr),l>>=1;l;l>>=1) res1 += sum[l];//Accumulate to root node
return resl;
}
At some point, only single-point modification interval queries and interval modification single-point queries will be used, when the zkw line treecode volumeThe advantages are great.
3. Interval query under single-point modification
Modify: directly change the value of the leaf node and then maintain it upwards.
Query: node values are directly accrued as the sentinel moves up.
//
inline update(int x,ll k){
x += P; tr[x] = k;
for(x>>=1; x ;x>>=1) tr[x] = tr[x<<1]+tr[x<<1|1];
}
inline ll query(int l,int r){
l += P-1; r += P+1;
ll res = 0;
while(l^1^r){
if(~l&1) res+=tr[l^1];
if(r&1) res+=tr[r^1];
l>>=1; r>>=1;
}
return res;
}
4. Single-point query under interval modification
Think of the process of assigning initial values as marking leaf nodes, and interval modifications as marking nodes.
Since the markers of the zkw line tree are permanent, the values of the markers are treated as the true values of the nodes at this point.
But this approach clearlyFor single-point queries onlyValid, you need to add all the tokens along the path from the node to the root when querying.
//
inline void update_add(int l,int r,ll k){
l += P-1; r += P+1;
while(l^1^r){
if(~l&1) tr[l^1]+=k;
if(r&1) tr[r^1]+=k;
l>>=1; r>>=1;
}
}
inline ll query(int x){
ll res = 0;
for(x+=P; x ;x>>=1) res+=tr[x];
return res;
}
5. Limitations of marking permanence
The above modifications and inquiries are all based onoperation has the law of union (math.), so the markers can be made permanent as a way to reduce the constants added by marker devolution.
But if the operationPriority exists, the markers can no longer be made permanent. Consider marking down (similar to a recursive line tree) and then updating from leaf nodes up when updating.
But if the optimization is devolved once by finding the child nodes one by one starting from the root like a recursive line tree, then the optimization is equal to nothing.
So consider decentralized operations based on the characteristics of the zkw line tree, and make it as simple and easy as possible.
So easy, search a purple coat.
V. Modifications and queries with arithmetic priorities
1. Marking for de-permanentization
The only nodes we will use when performing interval modifications exist on the chain from the sentinel node to the root.
So just consider decentralizing the node markers on these two chains.
(1) How to get what are the nodes that need to be decentralized and labeled
Consider the most violent methods:
Recurses upward from the sentinel node to the root node each time, devolving markers on backtracking.
Obviously the constant optimization in this way is approximately equal to zero.
Considering optimization is definitely based on the characteristics of zkw lineage trees.
Still, since the zkw lineage tree is a full binary tree structure, it is possible to pass the nodenumber transpositionway to find the number of all its parent and child nodes.
Obviously the chain from the sentinel to the root node is made up of all the fathers of the sentinel, so just have the sentinel number shifted.
(2) How to pass markers from top to bottom
Record the depth of the leaf nodes again.
Think about the nature of a full binary tree: it points to the root node number when the node number is shifted right by the depth of the node.
So the number of bits shifted to the right of a node, decreasing sequentially from the depth of the node, gives the number of all its father nodes from top to bottom.
2. Interval modification
Decentralize the markers first, then do the marker update normally.
Passing the markers may take into account the subtree size, which can be calculated directly by depth.
Take interval addition and multiplication as an example：
// Record leaf node depth when building the tree
P = 1;DEP = 0;
while(P<=n+1) P<<=1,++DEP.
//...
//...
//...
inline void update_add(int l,int r,ll k){
l=P+l-1; r=P+r+1.
//Delegate the markers first
for(int i=DEP;i;--i) push_down(l>>i,1<<i),push_down(r>>i,1<<i);
//push_dwon( node on chain , current subtree size ).
int siz = 1;
while(l^1^r){
if(~l&1) tr[l^1]+=siz*k,sum[l^1]+=k;//normal update
if(r&1) tr[r^1]+=siz*k,sum[r^1]+=k;
l>>=1; r>>=1; siz<<=1;
// Maintain the parent-child relationship
tr[l] = tr[l<<1]+tr[l<<1|1]; // since the markers have been decentralized, cumulative markers are no longer considered in maintenance
tr[r] = tr[r<<1]+tr[r<<1|1];
}
for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];//upload to root node
}
//
inline void update_mul(int l,int r,ll k){
l += P-1; r += P+1;
for(int i=DEP;i;--i) push_down(l>>i,1<<i),push_down(r>>i,1<<i);
while(l^1^r){
if(~l&1) tr[l^1]*=k,mul[l^1]*=k,sum[l^1]*=k;// mark overwrite
if(r&1) tr[r^1]*=k,mul[r^1]*=k,sum[r^1]*=k;
l>>=1; r>>=1;
tr[l] = tr[l<<1]+tr[l<<1|1];
tr[r] = tr[r<<1]+tr[r<<1|1];
}
for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];
}
3、Interval search
Lower the marker first.
Since the markers have been de-permanentized, it is straightforward to accumulate the node values.
//
inline ll query(int l,int r){
l = l+P-1;r = r+P+1; // put the markers first
// Decentralize the markers first
for(int i=DEP;i;--i) push_down(l>>i,1<<i),push_down(r>>i,1<<i);
ll res = 0;
while(l^1^r){
if(~l&1) res+=tr[l^1];
if(r&1) res+=tr[r^1];
// No need to accumulate marker contributions since the markers are decentralized
l>>=1; r>>=1;
}
return res.
}
VI. Optimization effect
1. Time complexity
It was also mentioned at the beginning: the bottleneck of a recursive line tree with a large constant is its need to perform the tree'srecursive traversalto find the target node and then backtrack for information maintenance.
zkw Line TreeJustOptimized to recursively find goal nodes likeiterative processThe constants of the
If you are looking for constants or focusing on optimized traversal, then the optimization of the zkw line tree is obvious; if you want to maintain more complex information, then obviously the constants are not quite enough, and you need to make improvements elsewhere.
2. Space complexity
zkw The line tree needs to be openedtriple space, the normal line tree requires four times the space to be opened if dynamic opening points are not used.
Compared to a normal line tree, the zkw line tree code is understandable and concise, with noforget to build up sthcap (a poem)forget to terminate recursionproblem, and the determinism of the full binary tree structure allows theHand-made dataIt's also more convenient.
For some topics with complex maintenance information, zkw line tree has the advantage of clearer thinking when pushing by hand.
If one is more introverted, one is afraid to use a recursive line segment tree to recursively maintain information.
What if you want to implement more and more powerful operations recursively with zkw!
zkw Line Tree Realization of Other Line Tree Structures
I. Introduction
1. About zkw line tree
In my opinion:specializationA zkw lineage tree is a tree that is built out as a full binary tree structure, where parent-child relationships between nodes are strictly defined, where all information is maintained from the leaf nodes upwards, and where the maintenance process is realized by cyclic recursion.
BTW: In Zhang Kunwei's PPT, it is mentioned that in order to minimize the constants brought by recursion, there areAssembly version of non-recursiveLine Segment Trees.
So my understanding is:generalizationThe zkw line tree refers to the tree that is passed through theLoop recursion instead of recursionRealized line segment trees.
2、About the optimization effect
Due to the nature of most line tree structures, which most of the time must loop up and down twice to maintain information, the zkw line tree is more optimized for the code'ssimplicitycap (a poem)ease of understanding(And, of course, there are some optimizations for constants).
II. Persistent Line Tree
1. Introduction
The difference between a persistent line tree and a normal line tree is that it supports modification and access to theAny version。
As an example: given a sequence\(a_N\), perform a million operations on it and then suddenly ask you for the sequence information after the tenth operation.
The plain idea is to build a line tree for each operation, with a space complexity of\(O(3mn)\) The.
It can be found:
After the modification, most of the nodes are not affected, so consider creating new corresponding nodes only for the affected nodes. The rest of the unaffected nodes are directlySharing nodes with the original tree, which is equivalent to creating a new modified line segment tree.
2、Single-point modification single-point query
After each single point modification, only the points on that chain from the leaf node to the root node are affected.
So we just need to create a new corresponding chain for the affected one, and the rest of the unaffected nodes are directly shared with the version to be modified.
For the position to be modified this time, after taking the original sequence\(a_N\) The nodes in the initial line segment tree created, whose corresponding leaf nodes in the chain to the root are respectively\(tl\)The current new node is\(now\), the next new node is\(new\)：
in the event that\(tl\) For the left son, then\(now\) The left son of\(new\)The right son is\(tl\) Sibling nodes corresponding to nodes in the tree to be modified;
in the event that\(tl\) For the right son, then\(now\) The right son of\(new\)The left son is\(tl\) Sibling nodes corresponding to nodes in the tree to be modified.
It is actually the position of the new node with the position of the node in the initial treecorresponding to。
Look at the diagram (the numbers inside the nodes are the node numbers): in theprimary sequenceModify a position on.
existAfter the first modificationon the sequence, and then modify it again:
Continuing inAfter the first modificationThe modifications are made on the sequence of the
We find that the position of the newly created chain in the new tree, compared to the position of the chain in the initial tree in the initial tree, isequalThe.
So when we create a new node, the position of the new nodefollowThe positions of the nodes in the corresponding initial tree are performedmobility。
Due to the need for inter-versionbase a distinction on the root node (computing)(since using leaf nodes would be very cumbersome), theModifications and inquiriesOperations can only be started from the root nodetop-downCarried out to prevent problems with different versions of storage.
So we need one more record: the left and right sons of the current node.
insofar as\(tl\) To the root of the chain how to quickly find, we talked about the "Sentinel" when we have talked about the implementation, the next step is to simulate the entire process of creating new nodes can be.
At the same time, the node number of the newly created node is incremented sequentially, and the operation is performed after theBottom-up maintenanceInformation is also handy:
//build the initial line segment tree
while(P<=n+1) P<<=1,++DEP; NOW = (1<<(DEP+1))-1;//number of last node
for(int i=1;i<=n;++i) read(tr[P+i]); rt[0] = 1;//initial tree root is 1
for(int i=P-1;i;--i) son[i][0]=i<<1,son[i][1]=i<<1|1;//record the child nodes 0 for left son; 1 for right son
//...
//...
inline void update(int i,int vi,int val,int l){
int tl = l+P;// the number of the corresponding leaf node in the initial tree
int v = rt[vi];//root of the line tree to be modified
rt[i] = l = ++NOW;//root of the new line segment tree
for(int dep=DEP-1; dep>=0 ;--dep,l = NOW){
//Simulate the node update process
if((tl>>dep)&1) son[l][0] = son[v][0],son[l][1] = ++NOW,v = son[v][1];
else son[l][0] = ++NOW,son[l][1] = son[v][1],v = son[v][0];
}
tr[l] = val;//update the last leaf node
//Maintain information from the bottom up (if needed)
//for(int dep=1;dep<=DEP;++dep) tr[l-dep]=tr[son[l-dep][0]]+tr[son[l-dep][1]];
}
The version query is the same as the modification, which simulates subtree selection starting from the root:
//
inline int query(int vi,int l){
int tl = l+P;// the corresponding leaf node number in the initial tree
l = rt[vi];// current version of root
for(int dep=DEP-1; dep>=0 ;--dep) l=son[l][(tl>>dep)&1];
return tr[l];//return leaf node value
}
3、Interval modification interval query
The information I have learned so far is:Can only do range plus。
Persistent line segment trees have a large number of common nodes, so markers can't be delegated and modifications should be able to be maintained with persistent markers, or they willImpact on other versions。
Then consider how to do zone plus.
- Marker Permanence: Omit marker decentralization to reduce constants while preventing effects on other versions;
- Subtree sizes are recorded during preprocessing, and marker values are accrued during checking.
The difference is:
- New nodes need to be created for the intervals;
- The modifications are moved against the trajectory of the nodes in the initial tree;
- Modifications need to be made from the top down, and then maintenance is done again from the bottom up (similar to recursive backtracking).
III. Weighted Line Tree
1. Introduction
Ordinary line segment trees maintain information, and weighted line segment trees maintainNumber of messages。
A weighted line tree is equivalent to opening a normal line tree with abarrel (of oil etc), which is used to process the number of messages toSingle-point modification and interval queryrealizationDynamic Global No.\(k\) oldest。
2、Query global ranking
The number of occurrences of node stock information in a weighted line segment tree:
//
inline void update(int l,int k){
l += P; tr[l] += k;//k is the number of occurrences of the message
for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];
}
The prefix sum of the relative size positions forward of the current number in thesecurity situationRanking in:
//
inline int get_rank(int r){// query the global rank of the rth number
int l = 1+P-1; // do the prefix sum of the interval [1,r]
r += P+1;
int res = 0;
while(l^1^r){
if(~l&1) res+=tr[l^1];
if(r&1) res+=tr[r^1];
l>>=1; r>>=1;
}
return res; }
}
3. Dynamic global section\(k\) oldest
Based on the structure of the line segment tree, the first\(k\) largethe equinoxThe implementation is actually in the line treeFind left and right subtreesThe process.
Query No.\(k\) When large, it is simulated with left and right subtree selection with the help of the structure of a line segment treethe two-part processReady to go:
//
inline int K_th(int k){
int l = 1,dep = 0; while(dep<DEP){
while(dep<DEP){
if(tr[l<<1]>=k) l=l<<1;// analog bisection
else k-=tr[l<<1],l=l<<1|1;
++dep;
}
return l-P;//subtract the imaginary point number to get the number in the original array
}
4. Predecessors and successors
Sometimes it is also necessary to inquire\(k\) The precursor and successor of the
\(k\) The precursors are: the largest less than\(k\) The number of;
\(k\) The successor of is: the smallest is greater than\(k\) The number of.
surname Zha\(k\) The precursor of can be viewed as: check with\(k-1\) of ranking the same number;
surname Zha\(k\) The successor of can be viewed as: the Chabi\(k\) The number of rankings that are one place behind.
Combine them.\(get\_rank\) cap (a poem)\(K\_th\) Ready to go:
//
inline int pre(int k){
int rk = get_rank(k-1);
return K_th(rk);
}
inline int nex(int k){
int rk = get_rank(k)+1;
return K-th(rk);
}
IV. Persistent Weighted Line Tree (Chairman's Tree)
I was anxious when someone said zkw couldn't do a Chairman's Tree.
1. Introduction
As the name suggests, thePersistent Line Tree and Weighted Line TreeCombined.
In most cases only interval queries need to be supported, commonly used to solve theStatic Interval No.\(k\) oldestThe reason for this is that a separate chair tree is not very good for modification operations.
Sure.Dynamic Interval No.\(k\) oldestimplementation - a tree within a tree - can jump directly to theCatalog VGo watch.
2. Static Interval No.\(k\) oldest
The Chairman's Tree maintains a line segment tree for each position of the sequence with node values that correspond to ranges of values on the sequence.
at the 16th meeting\(m\) on a tree of line segments, the interval\([L,R]\) Maintained: sequence on\(a_i\sim a_m\) How many of the numbers in the\([L,R]\) Scope.
We are interested in the sequenceWeights for each numberBoth open a line segment tree with a total of\(N\) tree, can't be stored, so use a persistent line tree.
Since the weights line tree stores the weights of the numbers, and the prefix sum is stored on each node, the information is additive. So look up\([L,R]\) tantamount to finding out\([1,R]-[1,L-1]\)。
A new book on persistent lineage trees and a query on weighted lineage trees would be nice to combine:
// Build a new tree for a persistent inline tree.
inline void update(int i,int vi,int l,int k){
int tl = l+P; int v = rt[vi]; int k
int v = rt[vi].
rt[i] = l = ++NOW;
for(int dep=DEP-1; dep>=0 ;--dep,l=NOW){
if((tl>>dep)&1) son[l][0] = son[v][0],son[l][1] = ++NOW,v = son[v][1];
else son[l][1] = son[v][1],son[l][0] = ++NOW,v = son[v][0];
}
tr[l] = tr[v]+k;//need to maintain prefix sums
//upward maintenance information
for(int dep=1;dep<=DEP;++dep) tr[l-dep]=tr[son[l-dep][0]]+tr[son[l-dep][1]];
}
// Query of the weighted inline tree
inline int query(int l,int r,int k){
// query [l,r] is equivalent to query [1,r]-[1,l-1]
l = rt[l-1];r = rt[r].
int tl = 1;//answer
for(int dep=0;dep<DEP;++dep){
int num = tr[son[r][0]]-tr[son[l][0]];//left subtree size
if(num>=k){// not larger than the left subtree, indicating that it is in the left subtree
l = son[l][0].
r = son[r][0].
tl = tl<<1;
}
else{// is larger than the left subtree, indicating that it is in the right subtree
k -= num;
l = son[l][1];
r = son[r][1];
tl = tl<<1|1.
}
}
return tl-P;// the current weight is: the corresponding position in the initial tree minus the number of the imaginary point
}
V. Tree arrays sets of weighted line segment trees
1. Introduction
Above, it was said that a separate chair tree is not easy to maintainDynamic Interval No.\(k\) oldest, mainly because the corresponding other version relationships were broken when the chair tree was modified.
Realization of Dynamic No.\(k\) The big plain idea is of course still to open a weighted line segment tree for each position of the sequence, so the difficulty lies in exactly which trees we have to modify.
due toWeighted line tree with additivityproperty, so we can take a tree array to maintain the prefix sums of the line trees and use it to find out which trees to modify. This is a process we can use with\(lowbit\) to realize.
Save the number of the tree to be modified, and then do the operation of adding the line tree, at which point the operation changes from multiple line trees to operating on a single line tree.
2. Initialization
If a zkw line tree is built for each point of the sequence, the space becomes\(Q(3n^2)\) s, so we need todynamic opening pointThe space complexity becomes\(O(n\log^2{n})\)。
(just store a node, we zkw also have to dynamically open the point, the parent-child relationship corresponds to the initial tree on it).
In order to ensure that the new tree nodes correspond to the sequence when modified and queried, as well as a strictly deterministic tree structure, so we first build an initial tree (There's no need to actually build it because we'll only be using the numbering), the nodes in the new tree at the time of the operationfollowThe nodes corresponding to the nodes in the initial tree are moved.
//
for(int i=1;i<=n;++i){
read(a[i]);
b[++idx] = a[i];
}
sort(b+1,b+1+idx).
idx = unique(b+1,b+1+idx)-(b+1); //discretize
while(P<=idx+1) P<<=1,++DEP;//find the initial tree node number spare
for(int i=1;i<=n;++i){
a[i] = lower_bound(b+1,b+1+idx,a[i])-b;
add(i,1);//build line segment tree for each position
}
//...
inline void update(int i,int l,int k){
int tl = l+P,stop = 0;
rt[i] ? 0 : rt[i]=++NOW;//dynamic open point
l = rt[i]; st[++stop] = l;tr[l] += k;
for(int dep=DEP-1;dep>=0;--dep,st[++stop]=l,tr[l]+=k){
if((tl>>dep)&1) son[l][1]?0:son[l][1]=++NOW,l=son[l][1];
else son[l][0]?0:son[l][0]=++NOW,l=son[l][0];
}
//For convenience you can also save all the nodes in the chain before doing maintenance
//while(--stop) tr[st[stop]] = tr[son[st[stop]][0]]+tr[son[st[stop]][1]];
}
inline void add(int x,int k){//lowbit find the line tree that needs to be used
for(int i=x;i<=n;i+=(i&-i)) update(i,a[x],k);
}
3、Single point modification
First subtract the weight of the original number by one, then let the new number be weighted by one.
//
inline void change(int pos,int k){
add(pos,-1);
a[pos] = k;
add(pos,1);
}
4、Query interval ranking
Since the weighted lineage tree maintains a prefix sum, it is useful to put the interval\([L,R]\) The query is viewed as a query\([1,R]-[1,L-1]\)。
Just use the tree array to find the line tree you need to use, then do the line tree sum and find the prefix sum.
//
inline int query_rank(int l){
l += P; int res = 0; int
l += P; int res = 0; int
for(int dep=DEP-1;dep>=0;--dep){
if((l>>dep)&1){//Do line tree sum for prefix sums
for(int i=1;i<=tmp0;++i) res-=tr[son[tmp[i][0]][0]],tmp[i][0]=son[tmp[i][0]][1];
for(int i=1;i<=tmp1;++i) res+=tr[son[tmp[i][1]][0]],tmp[i][1]=son[tmp[i][1]][1];
}
else{
for(int i=1;i<=tmp0;++i) tmp[i][0]=son[tmp[i][0]][0];
for(int i=1;i<=tmp1;++i) tmp[i][1]=son[tmp[i][1]][0];
}
}
return res;
}
inline int get_rank(int l,int r,int k){
tmp0 = tmp1 = 0; }
for(int i=l-1; i ;i-=(i&-i)) tmp[++tmp0][0] = rt[i];
for(int i=r; i ;i-=(i&-i)) tmp[++tmp1][1] = rt[i];
return query_rank(k)+1;
// query_rank finds the number of numbers less than or equal to k, plus one is k's rank.
}
5. Dynamic Interval No.\(k\) oldest
Same reasoning as query ranking: since the weighted lineage tree maintains prefix sums, it is useful to put the interval\([L,R]\) The query is viewed as a query\([1,R]-[1,L-1]\)。
Still, first use the tree array to find the line tree you need to use, and do the line tree sum when querying. Then just simulate bisection on the line segment tree.
//
inline int query_num(int k){
int l = 1; for(int dep=0,res=0;dep<DEP;++dep,res=0){
for(int dep=0,res=0;dep<DEP;++dep,res=0){
for(int i=1;i<=tmp0;++i) res-=tr[son[tmp[i][0]][0]];
for(int i=1;i<=tmp1;++i) res+=tr[son[tmp[i][1]][0]];//node values of each tree satisfy summable
if(k>res){
k -= res;// do the tree bisection
for(int i=1;i<=tmp0;++i) tmp[i][0]=son[tmp[i][0]][1];
for(int i=1;i<=tmp1;++i) tmp[i][1]=son[tmp[i][1]][1];
l = l<<1|1;
}
else{
for(int i=1;i<=tmp0;++i) tmp[i][0]=son[tmp[i][0]][0];
for(int i=1;i<=tmp1;++i) tmp[i][1]=son[tmp[i][1]][0];
l = l<<1;
}
}
return l-P;//leaf node corresponding number
}
inline int get_num(int l,int r,int k){
tmp0 = tmp1 = 0;//first use lowbit to find the line tree to be queried
for(int i=l-1; i ;i-=(i&-i)) tmp[++tmp0][0] = rt[i];
for(int i=r; i ;i-=(i&-i)) tmp[++tmp1][1] = rt[i];
return query_num(k);
}
Line Segment Tree over Line Segment TreeThe same principle applies to it. The lower line segment tree maintains the sequence information and then an upper line segment tree is used to maintain the prefix sum of the lower line segment tree.
You can see the chart, I won't go into much detail for now:（"I can't really write.)
VI. Rabbit team line segment tree
(I'm not particularly familiar with it, so for the time being it's only information that has asubtractability(Interpretation)I was anxious when someone said zkw couldn't do a rabbit team line segment tree.
1. Introduction
Rabbit team line segment trees refer to a class: in information modificationat the same timein order to\(O(\log{n})\) Complexity do maintenance of line segment trees. Supports single-point modification interval queries, which are typically used to maintain thePrefix Maximumof the problem.
(Pink Bunny in)this article(which was the first to be described in the)
2. Handling and maintenance
The general way in which it processes and maintains information can be seen as:
- First change the information and then do the maintenance from bottom to top;
- Upward maintenance maintains the information from bottom to top again for every node reached;
- The second time it is maintained from bottom to top, the left subtree contribution to the answer remains unchanged and only the right subtree contribution to the answer is considered.
Since the first upward maintenance requires a second maintenance of all its subtrees starting from the current node, a common method for recursive line segment trees is toquadratic recursionProcesses right subtree information.
3. Specific realization
Consider how to use a zkw line treerecursive (calculation)Processes right subtree information.
First, after making changes to the single pointbottom topProcessing and maintenance is performed, and the node depth is recorded to prevent out-of-bounds from occurring during the second maintenance:
// After a single point of modification, each upload updates to the root node
inline void update(int l,ll k){
l += P;int dep = DEP.
mx[l] = k;mn[l] = k;//...
for(l>>=1,--dep; l ;l>>=1,--dep) push_up(l,dep);
}
Then, simulate the marker upload process again:
//
inline void push_up(int l,int dep){
mx[l] = max(mx[l<<1],mx[l<<1|1]);
//...
ans[l] = ans[l<<1]+calc(l<<1|1,dep+1,mx[l<<1]);
}
inline int calc(int l,int dep,ll mx){
int res = 0,tl = l.
while(dep<DEP){/simulate the left and right subtree selection process
if(mx[l]<=k) break;//pruning and so on
if(mx[l<<1]<=k) l = l<<1|1;
else{
res += len[l]-len[l<<1];// information has reducibility, consider left interval coverage
l <<= 1;
}
++dep;
}
if(dep==DEP) res += (mx[l]>k);//leaf node special judgment
}
VII. Kinetic Tournamen Tree
(A reader commented asking if it was possible to implement KTT, and we discussed and researched it and found that it was.)
1. Introduction
KTT was initially launched in2020 Training Team EssaycomprisingEI The captain offered.
KTT used to maintainDynamic Interval Maximumproblem, the basic idea of which is to view the information to be maintained as thelinear function (math.), all modifications are made based on the function. Also set thethresholds, indicates when the value of the maintained answer is changed, and violently reconstructs the subtree to maintain the answer when the modified or queried information reaches a threshold value.
The author feels that learning KTT is best started with some specific questions. So what we have below, therevolve entirely aroundThe classic problem mentioned in the paperSubchapter VI of P5693 EITo carry out the unfolding.
2. Information processing
The largest sub-segment and the four messages to be recorded are maintained in a line segment tree and categorized for discussion when the messages are merged:
- \(lmax = \max(lmax_{ls},sum_{ls}+lmax_{rs})\)；
- \(rmax = \max(rmax_{rs},sum_{rs}+rmax_{ls})\)；
- \(mx = \max(mx_{ls},mx_{rs},rmax_{ls}+lmax_{rs})\)。
carry outdynamic (science)Maintenance is going to be with KTT, and that's what we're focusing on.
Instead of a specific value, each message now records anlinear function (math.)：\(f(x)=kx+b\)。
included among these\(k\) is the length of the largest sub-segment.\(x\) is the amount of change.\(f(0)=b\) A specific value for the current maintenance.
Also, for both functions, record athresholds\(dx\), which indicates whether the current interval maximum is carried out between the two functionsin turn。
3. On alternating thresholds
Prior knowledge:Renjiao 8th Grade Book 19.2.3 Primary Functions and Equations and Inequalities
After combining the two functions to takemaximum valuesWhen you do, you need to know exactly what you shouldwhen?Which function to pick. We know that we should look at the position of the intersection of the functions relative to the interval to categorize the discussion of the taking cases.
The alternation threshold does just such a thing, optimizing time complexity by keeping track of when the function selection should be alternated at maintenance time, and only alternating when alternation is needed.
Specifically, wheninterval (math.)\(q\) When the function is shifted upward, the intersection of the function is shifted left and right relative to the interval. At this point we makethresholds\(dx\) diminishregard as\(dx<0\) when it indicates that the function selected at this point is going to be alternated.
Exactly how much does it decrease, since the functions all satisfy\(k\ge 1\), so it is necessary to make at least\(dx-=q\)(Preferably this number, of course; subtracting more would be too many refactorings).
Since the same interval may be maintained by two different functions, when merging intervals, the threshold should not only minimize for the left and right intervals, but also include the intersection of the two current functions.
4. Interval and function merging
The author's personal recommendation is to writeoverloaded operatorForm.
Operations against functions are intersection finding, function merging, and function moving:
//struct Func
inline Func operator + (const Func&G) const{//function merge
return Func(k+,b+);
}
inline ll operator & (const Func&G) const{//Finding the point of intersection
return (-b)/();
}
inline void operator += (const ll&G){//The function moves up
b += k*G;
}
For interval merging, we simply categorize the discussion on the basis of function manipulation, taking care to maintain the threshold information at the same time:
//struct Tree
inline bool operator < (const Func&G) const{
//Confirm the relative position of the two functions to determine if there is an intersection.
return k== && b< || k<;.
}
inline void Merge_lx(Func x,Func y,Tree &tmp) const{//find lmax
if(x<y) swap(x,y);
if(>=) = x;//Chin set over the function position, at this point the two functions do not intersect
else = y, = Min(,x&y);
}
//...
inline Tree operator + (const Tree&G) const{//Interval merge
Tree tmp; = sum+; = Min(dx,); //note maintenance of threshold information
Merge_lx(lx,sum+,tmp);Merge_rx(,+rx,tmp).
Merge_mx(,mx,tmp);Merge_mx(,rx+,tmp);
return tmp;
}
5. Modification and refactoring
The interval addition follows the normal way, the only difference being that the node subtrees need to be modified after thereconstruct。
The first step is definitely to decentralize the markers:
//struct Tree
inline void operator += (const ll&G){//interval (math.)
lx += G; rx += G; mx += G; sum += G; dx -= G;
}
//
inline void push_down(int p){//normalcypush_down
if(tag[p]){
tag[p<<1] += tag[p]; tr[p<<1] += tag[p];
tag[p<<1|1] += tag[p]; tr[p<<1|1] += tag[p];
tag[p] = 0;
}
}
Then do the modifications normally:
//
inline void update(int l,int r,ll k){
l += P-1; r += P+1;//formerpush_down
for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
while(l^1^r){
if(~l&1) tag[l^1]+=k,tr[l^1]+=k,rebuild(l^1);//Don't forget to refactor.
if(r&1) tag[r^1]+=k,tr[r^1]+=k,rebuild(r^1);
l>>=1;r>>=1;
tr[l] = tr[l<<1]+tr[l<<1|1];
tr[r] = tr[r<<1]+tr[r<<1|1];
}
for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];
}
For refactoring, it starts from the root node of the current subtree and recurses down one layer at a time until there are no nodes to be refactored:
//
inline void rebuild(int p){
if(tr[p].dx>=0) return ;
int head = 1,tail = 0;
st[++tail] = p; push_down(p);
while(tail>=head){//analog stack
int ttail = tail;
for(int j=tail,pos;j>=head;--j){
pos = st[j]; //See if the subtree of the child node needs to be updated
if(tr[pos<<1].dx<0) st[++tail]=pos<<1,push_down(pos<<1);//take note ofpush_down
if(tr[pos<<1|1].dx<0) st[++tail]=pos<<1|1,push_down(pos<<1|1);
}
head = ttail+1;
}//Re-maintenance
do{ tr[st[tail]]=tr[st[tail]<<1]+tr[st[tail]<<1|1]; } while(--tail);
}
6. Enquiry
Just do the query normally.
One thing to keep in mind is that interval merging is doneIn left-right orderConducted.
//
inline ll query(int l,int r){
l += P-1; r += P+1;//formerpush_down
for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
Tree resl,resr;
while(l^1^r){
//Note the order in which the left and right intervals are merged
if(~l&1) resl = resl+tr[l^1];
if(r&1) resr = tr[r^1]+resr;
l>>=1;r>>=1;
}
return (resl+resr).;
}
The basic idea of KTT is this, converting information into functions for processing while maintaining thresholds for reconstruction. This gives KTT a complexity superior to chunking, but also imposes limitations on its use.
By now, it's safe to assume that a zkw line tree does basically everything a recursive line tree can do.
Some template questions and codes
let gocloud clipboardup and will follow the article updates.
postscript
Update Log
The author's current learning is too shallow, most of the content of the article is the author's own understanding, there may be places that are not very clear. When the author learns something new, he will first update it in thethis articleas well asMy Blog, and then find time for a unified update.
At the same time, the author will often modify and improve the content details and code blocks of the article, if you have any ideas you can put forward, let's work together to solve the problem. The author is really really live!!!
We look forward to your valuable suggestions.
express gratitude (esp. in public)
The Power of Statistics" Tsinghua University - Kun-Wei Zhang / organized by hzwer
OIWiki
CSDN IXJX
Tifa's Blog [Rock Valley Daily #35] Tifa
L.A. Daily #4 Bright Moon, Half Sprinkled Flowers
NianFeng // EntropyIncreaser //
For reprints, please cite the source.