A potentially new type of Segment Tree

[bethandtownes]

Hi~ I found a problem that could potentially lead to a new type of segment tree. The problem is here. https://leetcode.com/problems/design-excel-sum-formula/ . In case you don't have subscription, here is a link that contains the description of the problem: https://www.cnblogs.com/grandyang/p/7170238.html

Here is my solution: https://www.acwing.com/solution/LeetCode/content/8771/

Although I didn't use a segment tree for this problem because its input size is small, I think segment tree could be used as well. However, instead of monoid on sum of int, it is probably on a monoid on sum of the evaluation functionals (in cpp, its a std::function<int(void)>, which to me seems like the double dual (recall that in functional analysis, there is a canonical embedding from the double dual into the original space, I think there is more general version of this phenomeon in category theory but I am not sure). It is this canonical embedding made me feel like a segment tree is eligible for this. It would be great if you can share your insights on this.

Thanks! Jason

[kmyk]

Your technique seems just using std::function<int(void)>. I don't like to call this a lazy evaluation or lazy propagation in segment trees because they also mean memoizing the calculated values in some ways. But your technique doesn't memoize.

Also, I suspect the relation to dual spaces. Your technique sends x ∈ X into φₓ : { 0 } → X, but an element of double dual space is Ψ : (V → F) → F. That seems less related. (By the way, is the next sentence is a typo of an embedding from the original space into the double dual?)

there is a canonical embedding from the double dual into the original space

---

However, there is an interesting relation to segment trees for this LeetCode problem. We can generalize sequences to trees using dynamic trees (e.g. link cut tree, top tree), and we can computes various monoid sums on trees in O(log V), instead of sequences (e.g. this problem (Japanese, but enough simple)). So, we can say that the problem at LeetCode is a problem that uses DAGs instead of trees or sequences.

[bethandtownes]

(By the way, is the next sentence is a typo of an embedding from the original space into the double dual?)

Yes. It was a typo. I think the injection is in the reverse direction (https://math.stackexchange.com/questions/3463970/intuitively-understanding-double-dual-of-a-vector-space).

I think you are right in that the connection (if any) between this problem and the double dual is at most weak. I should have put more thought into it before presenting my argument. Looking back, that comment look a bit amateur.

As for the lazy evaluation part. my understanding is that the use of std::function<int(void)> delays the evaluation of the sum of cells until get() is called. According to the definition of thunk, `

In computer programming, a thunk is a subroutine used to inject an additional calculation into another subroutine. Thunks are primarily used to delay a calculation until its result is needed, or to insert operations at the beginning or end of the other subroutine. `,

the design with std::function seems to fit this description a little bit, although I am not quite sure.

So, we can say that the problem at LeetCode is a problem that uses DAGs instead of trees or sequences.

I get the point although I don't know how to translate this into code. In my code, traversing in topological order of the DAG was encoded inside the evaluation of the std::function. Can we do a similar thing inside a segment tree? (If I am not mistaken, you are refering to efficiently folding arbitrary intervals w.r.t a monoid of a DAG in its topological order using Segment Tree?)

[kmyk]

lazy evaluation

As for the lazy evaluation part. my understanding is that the use of std::function<int(void)> delays the evaluation of the sum of cells until get() is called.

The "delay" of lazy evaluation (and "thunk") changes only the timing of computation, not inputs nor outputs (because they are words about evaluation strategy). You can get same results if you doesn't delay. However your "delay" changes also the values. Your code must delay computations to get correct results. Therefore, I agree that your usage of std::function<int(void)> has a relation to "delay", but the meaning of "delay" differs from the "delay" of lazy evaluation or lazy propagation.

DAG

how to translate this into code

You can think following problem: For a given DAG G whose each vertex v has a weight _av of a monoid M, compute following queries:

1. remove a directed edge
2. add a directed edge
3. update a weight of a vertex
4. compute (\sum_{path from v to u} _au) for a given vertex v

The LeetCode problem is an obfuscated version of this problem. To translate, you can construct and traverse the DAG directly.

Can we do a similar thing inside a segment tree?

Yes, but you need to think a dynamic version of segment tree (i.e., do cut & paste sequences). (Of course, if you were use std::function directly, it might become like just a doubly linked list rather than a segment tree)

[bethandtownes]

Okay. I will see if I can come up a segment tree variant using std::function.

On the other hand, I am waiting for the OJ www.acwing.com to release its public API. Once that is release, I will add it to the online judge tools. It is a new OJ founded by a Chinese Ex-Googler. It contains plenty of good library checking problems as well as Google KickStart problems.