For sets \(A,B\), let \(A\dotdiv B=(A-B)\cup(B-A)\) be their symmetric difference.
The set of finite covers of set \(A\) is \[\bigcup_{k\in\mathbb{N}}\{\{A_1,\dots,A_k\}\mid A_i\subseteq A, A_1\cup\dots\cup A_k=A\}\]
The set of finite partitions of set \(A\) is \[\bigcup_{k\in\mathbb{N}}\{\{A_1,\dots,A_k\}\mid A_i\subseteq A, A_1\cup\dots\cup A_k=A_1\dotdiv\dots\dotdiv A_k=A\}\]
For \(A'\subseteq A\), let \(\chi_{A'} \in \{0,1\}^A\) be the characteristic function of set A’.
\[a\in A' \leftrightarrow \chi_{A'}(i)=1\]
Let \(I\) be some finite set.
Consider the set system, \(2^{I}\) and integer set function \(f\in\mathbb{Z}^{2^{I}}\). \(f\) is modular when the following holds
\[f(J_1\cup J_2)+f(J_1\cap J_2)=f(J_1)+f(J_2)\]
Let \(s\in\mathbb{Z}^I\). \(f(J)=\sum_{i\in J}s(i)\) is modular.
segment trees
Let \(I=[0,2^k)\): \(I\) is an interval over the natural numbers.
Let \(S(l,j)=[2^{l}j,2^l(j+1))\). \(S(l,j)\) is a dyadic interval
Now, consider the following family of intervals over \(I=[0,n)\):
\[F = \bigcup_{l \in [0,k]}\{S(l,j)\mid j\in [0,2^{k-l})\}\]
\((F,\subseteq)\) is a laminar set family. Since there’s a unique maximum element, \(F\) is a tree. Sets \(S(l-1,2j)\) and \(S(l-1,2j+1)\) partition \(S(l,j)\).
It follows from modularity of \(f\) and the tree structure of \(F\subseteq 2^{I}\) that:
\[f(S(l,j))=f(S(l-1,2j))+f(S(l-1,2j+1))\]
Consider this algorithm.
Split(\(l, j,
J\)):
if \(S(l, j) \cap
J=\emptyset\) then
return \(\emptyset\)
if \(S(l, j) \subseteq
J\) then
return \(S(l,
j)\)
else
return \(Split(l-1, 2j, J)
\cup Split(l-1, 2j+1, J)\)
\(Split(k,0,J)\subseteq F\) partitions \(J\)
This can be used to solve problems involving range updates and
queries over sequences. Here’s a C++ excerpt from a
solution to such a problem. Ignore the
"lazy" segment trees.
if (disjoint(c,d,a,b)) {
return 0;
}
else {
if (subseteq(c,d,a,b)) {
return f_S[l][j];
}
else {
long long left = get(lazy1_f_S, lazy2_f_S, f_S, k, l-1,2*j,a,b);
long long right = get(lazy1_f_S, lazy2_f_S, f_S, k, l-1,2*j+1,a,b);
return left + right;
}
}