cp-blog/historic-segtree/

[utterances-bot]

Historic Information on Segment Trees | Yet Another Competitive Programming Blog

It’s been a while, but I’m back with some more estoric knowledge! Historic information is a concept I’ve only seen briefly mentioned in this tutorial on segment tree beats, and the section only covers one example of it, so I’ll cover some more examples in this article.

https://mzhang2021.github.io/cp-blog/historic-segtree/

[mariano22]

I think it's not necesary to store the timestamp. See the solution of Paimont Segment Tree: https://zhuanlan.zhihu.com/p/441174109

You can store in each node: x_1 = length of the segment node x_2 = sum of a_i x_3 = historical sum of a_i

Let X vector of each node as [x_1, x_2, x_3]

Then you can represent the a[l..r]+=k operation as a linear combination of X that only depend on k.

You have to modify the implementation of the segment tree because it's important to apply an update with +=0 to all nodes that are not affected (to make the time pass).

See: https://heartfirey.blog.csdn.net/article/details/127153950?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-1-127153950-blog-124817979.235%5Ev38%5Epc_relevant_anti_t3_base&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-1-127153950-blog-124817979.235%5Ev38%5Epc_relevant_anti_t3_base&utm_relevant_index=2

[mzhang2021]

@mariano22 Yeah my coach told me about the matrix interpretation shortly after I posted this as well, that is a much better and less error prone way of handling these types of updates 🙂. At the time I only knew of the timestamp based approach that I came up with myself for solving https://codeforces.com/gym/103069/problem/G

[mariano22]

Thank you for the problem! I imagine that sometimes historic accumulation operation can not be represented by a matrix multiplication (maybe if b_i *= a_i after each operation?).

The keys ideas of "Paimont Segment Tree" are 2 in my criteria: 1 - Notice you can represent states by 4-dim vectors and updates by matrix A_k (for any k) so we can compose updates using matrix multiplication. 2 - Notice that historic data accumulation (b_i += a_i after each operation) is an operation itself (that applies to all the range) and can be represented by applying A_k to the query range and A_0 to the complementary range. This observation is not trivial (at least not for me) and I struggled a lot coming up with this observation. I imagine that it's useful for any problem that requires historic data: to think that historic accumulation is an operation itself that affect differently the query range and the complement.

The timestamp idea is great btw!