Practice: Fenwick and segment trees
0 of 4 solved
About these problems
Apply, Connect, Reason and Stretch describe difficulty within this topic, not an official contest rating. Open any problem in any order; reading the chapter first is optional.
- 1Live range totalsMaintain an array. Type 1 p x assigns a[p]=x. Type 2 l r asks the inclusive range sum.ApplyNot started
- 2Live range minimumMaintain an array. Type 1 p x assigns a[p]=x. Type 2 l r asks the minimum value in the inclusive range.ConnectNot started
- 3Locate the kth tokenPosition i holds a_i tokens. Type 1 p d adds d to a[p], and the resulting count is guaranteed nonnegative. Type 2 k asks for the first position whose cumulative token count is at least k. Each such k is guaranteed between 1 and the current total.ReasonNot started
- 4Live subtree rewardsRoot a tree at 1. Type 1 v x assigns vertex v reward x. Type 2 v asks for the sum of rewards in v's subtree, including v.StretchNot started