转置原理可以直接对答案向量转置，这样避免了原问题非线性变换。
大体步骤是：转置，给转置问题找一个组合解释，解决转置问题，转置回去。但我好像也没有完全理解整个过程，所以写的有点意识流。
区间加、单点求值
考虑对答案向量转置，要求：
\(w\) 是输入向量。我们要解决 \(w=1\) 的问题，根据转置原理：
该问题和原问题的计算复杂性等价。然后我们就是要求 \(ans_i\) 关于 \(w_i\) 的线性组合。然后这个问题肯定可以线段树对吧，令 \(s_i\) 是线段树上每个节点存储的值，设计一个输入向量：
其中 \(w\) 由输入给出，\(s\) 和 \(ans\) 初始全是 \(0\)。你肯定会说这个输入向量形式和转置以后的形式不一样，但转置原理只是说了 \(Mx\) 和 \(M^Tx'\) 的计算复杂性相同，这个输入向量肯定能解决 \(M^Tx'\) 吧。你就说是不是能做.jpg
我们将所有步骤都写成若干初等矩阵相乘，\(P_1(i,j)\) 代表交换，\(P_2(i,k)\) 代表将第 \(i\) 行乘 \(k\)，\(P_3(i,j,k)\) 代表将第 \(j\) 行的 \(k\) 倍加到第 \(i\) 行上，然后写一下发现三种矩阵转置以后前两种不会改变；第三种会变成 \(P_3(j,i,k)\)。
考虑初始化，那就是对于每一个 \(w_i\)，会有一个对应的 \(s\) 集合 \(S_i\)，做 \(\forall s_j\in S_i,P_3(s_j,w_i,1)\)。然后修改就是 \(P_3(ans,s_i\times v,1)\)，查询就是 \(P_3(s_j,w_i,-1)\)。这样转置问题被我们在 \(O(q\log n+n\log n)\) 时间，\(O(n)\) 空间内解决了，说明原问题也可以在同样的时空复杂度内解决。
然后你发现这个转置到原问题的过程不太好理解啊，直接生硬转置的话由于所有变换都是方阵，所以我们的输入向量仍然是这个 \((q+2n)\times1\) 的向量，然后你觉得什么锤子，我们的原问题输入只有一个数啊？？考虑原问题的线性变换矩阵是 \(r\times c\) 的，于是乎输入向量为 \(c\times1\)，输出向量为 \(r\times1\)。转置以后显然两者规模互换，本质就是将输入和输出进行对偶，于是转置回去也只需要做这个对偶的过程就好。
对答案向量直接转置避免了不知道怎么转置的问题，并不意味着所有东西都可以通过转置来解决，因为转置以后的问题也不一定更简单，你的操作也不一定是线性变换。
省集题
这个题目展示了通过倒序处理转置之后的问题来实现在线做原问题，很神奇。
具体做法去看题解吧。经过和离心龙的讨论之后，他声称不需要转置，可以直接用线段树套可持久化平衡树维护折线，不过后面又声称自己假了。
所有问题大概都可以这么来转置，但要注意转置后的算法必须是完全的线性变换。这在生成函数视角有很好的应用，2026 年再研究吧。至于这样转置和别的方法是否会造成新问题难度上的差异，我只能说不知道。