[1] Binary search on a segment tree

In addition to updates to \(1\) element, this problem asks us to process the following queries:

• Type \(2\): Fix the left endpoint \(l\) and find the smallest \(r\) such that \(\sum_{i=l}^{r}A_i\geq t\).
• Type \(3\): Fix the right endpoint \(r\) and find the largest \(l\) such that \(\sum_{i=l}^{r}A_i\geq t\).

Since \(A_i\geq 0\), the interval sum is nondecreasing as the interval expands. We can use this monotonicity for binary search.

For example, for a type \(2\) query, computing each interval sum with a segment tree in \(O(\log N)\) time and performing binary search on \(r\) gives an \(O(\log^2 N)\) solution per query.

Furthermore, using a segment tree to combine the interval sum calculation and binary search lets us process each query in \(O(\log N)\) time. Following the names in AtCoder Library, we call these operations max_right and min_left.

This editorial explains how to implement max_right in \(O(\log N)\) time. The idea for min_left is similar, so we omit its explanation.

A simple implementation that performs binary search on \(r\) or \(l\) in \(O(\log^2 N)\) time per query is sufficient to obtain AC for this problem. You can also use this problem to prepare library implementations of max_right and min_left, or to check how to use a library.

---

[2] Implementing max_right

[2.1] The specification of max_right

First, use \(0\)-indexed half-open intervals.

Define max_right(L,t) as the operation that finds the largest integer \(R\) satisfying

\[ \sum_{i=L}^{R-1}A_i<t. \]

Here, \(L\leq R\leq N\), and the sum over an empty interval is \(0\).

Since all \(A_i\) are nonnegative, the interval sum is nondecreasing as \(R\) increases. Therefore, the values of \(R\) satisfying the condition form a contiguous range.

In this problem, \(t\geq 1\), so an empty interval always satisfies the condition.

The \(R\) returned by max_right(L,t) is the largest right endpoint satisfying the condition. If \(R<N\), adding the next element \(A[R]\) makes the condition fail. We can use this to obtain the answer to a type \(2\) query.

[2.2] A recursive implementation

First, construct a regular segment tree in which dat[i] stores the sum over the interval it represents. Assume that the sequence length N is stored in a global variable. Set extra leaves to \(0\).

As with a regular segment tree, pass the interval represented by each node as function arguments.

Suppose node \(i\) represents \([\mathrm{node\_L},\mathrm{node\_R})\).

Examine intervals from left to right, keeping the sum of the elements accepted so far in sum.

Process node \(i\) as follows:

1. If the node’s interval is to the left of the search starting position \(L\), do nothing.
2. If the entire node interval is contained in \([L,N)\) and sum + dat[i] < t, accept the whole interval and update sum.
3. If the whole interval cannot be accepted, recursively examine the children.
4. If we reach a leaf, it is the first position where the condition fails.

The sample implementation returns the first position where the condition fails, or \(N\) if there is no such position.

// dat[i] stores the sum over the interval represented by node i
// Examine [node_L, node_R) from left to right
// sum is the sum over the intervals accepted so far
int max_right_rec(int i, int node_L, int node_R,
                  int L, ll t, ll& sum) {
  if (node_R <= L) return N;

  // Can we accept the whole interval represented by this node?
  if (L <= node_L && sum + dat[i] < t) {
    sum += dat[i];
    return N;
  }

  // At a leaf, this is the first position where the condition fails
  if (node_R - node_L == 1) return node_L;

  int m = (node_L + node_R) / 2;
  int x = max_right_rec(2 * i, node_L, m, L, t, sum);
  if (x != N) return x;
  return max_right_rec(2 * i + 1, m, node_R, L, t, sum);
}

int max_right(int L, ll t) {
  ll sum = 0;
  return max_right_rec(1, 0, seg_size, L, t, sum);
}

Here, sum represents the sum over the intervals already examined and accepted. If a whole node can be accepted, we do not visit its descendants. We examine the children only when it cannot be accepted.

[2.3] Time complexity

First, for nodes containing the search starting position \(L\), move to the right child as needed to examine intervals contained in \([L,N)\).

After that, do not explore descendants of a node whose whole interval can be accepted; recursively explore only nodes that cannot be accepted.

Since \(A_i\geq 0\), if a node completely contained in \([L,N)\) cannot be accepted as a whole, the answer lies inside it. Therefore, outside the path leading to the answer, we can accept the whole node and finish exploring it.

Considering the paths to the search starting position \(L\) and to the answer position, we only need to examine nodes on these paths and their siblings.

The complete binary tree has height \(O(\log N)\), so the time complexity is \(O(\log N)\).

[2.4] Sample solution

• Sample solution: https://atcoder.jp/contests/aalc001/submissions/79977854

---

[3] Using AtCoder Library

AtCoder Library’s atcoder::segtree provides max_right and min_left.

• “Segtree” (AtCoder Library)

Use a segment tree that maintains interval sums. For max_right and min_left, specify a predicate on the interval information. Here, the predicate is “the interval sum is less than \(t\).”

For example, use max_right as follows:

auto check = [&](ll x) -> bool {
  return x < t;
};

int R = seg.max_right(L, check);

Use min_left similarly:

int L = seg.min_left(R, check);

Each query takes \(O(\log N)\) time.

• Sample solution: https://atcoder.jp/contests/aalc001/submissions/79977830