algorithm - 反转数组查询

Question

我有一个大小为 N 的数组，我给出了 2 种类型的查询

1 L R 反转 [L,R] 中的所有元素
2 L 求索引L处的值。

Example: [1,2,3,4,5]
1 2 4   -> [1,4,3,2,5]
1 4 5   -> [1,4,3,5,2]
2 5    -> 2

Q-查询次数
Q<=10^5 和 N<=10^5
直接解决方案将是 O(Q*N) 这将非常慢，如何使它更快可以使用线段树？

Answer 1

我不确定线段树算法是什么样的。

这可以在 O((n + q) log n) 时间内使用装饰的拉伸(stretch)树完成。每个节点装饰都包含一个后代计数和一个位，设置后会隐式翻转整个子树。要查询，请使用后代计数导航到正确的节点。要从 u 反转到 v，展开 u 到根，分离它的左子树 u.L，展开 v 到根，分离它的右子树 v.R，反转所有 u.L，v，v.R，将u.L重新附加到v.R来自的字段，展开u，重新附加v.R同样。

Key: ? denotes an anonymous node
     ^ denotes a subtree


   u
  / \
u.L  ?
 ^  / \
   v   ?
   ^   ^


u.L    v
 ^    / \
     u  v.R
      \  ^
       ?
       ^


v.R    v     # v's flip bit is inverted
 ^    / \
     u  u.L  # so is u.L's, for no effect on u.L
      \  ^
       ?
       ^


   u
  / \
v.R  v
 ^  / \
   ?  u.L
   ^   ^