Introduction

Suppose you have a fixed-length boolean array that starts entirely false, supports one-way updates from false to true, and needs three operations: val(i) in O(1), change(i) in amortized O(1), and find(i) for the nearest false index in O(log n). That mix of requirements is unusual enough that a plain array or a plain balanced tree is not quite the right answer on its own.

Why the One-Way Update Matters

The crucial detail is that values only change in one direction:

• initial state: all false
• updates: false -> true
• never: true -> false

That monotonic behavior makes a segment-tree-style summary structure attractive. Each internal node can store whether all values in its interval are true. If an interval is not fully true, then it still contains at least one false, which is exactly what find(i) needs to discover quickly.

Store the Raw Values Plus an Interval Tree

Keep two representations:

• a plain boolean array for val(i) in O(1)
• a segment tree where each node stores the logical AND of its interval

If a segment tree node is:

• 'true, then every element in that interval is true'
• 'false, then at least one element in that interval is still false'

Here is a simple Python implementation:

1class FalseFinder:
2    def __init__(self, n):
3        self.n = n
4        self.values = [False] * n
5        self.tree = [False] * (4 * n)
6
7    def val(self, i):
8        return self.values[i]
9
10    def change(self, i):
11        if self.values[i]:
12            return
13        self.values[i] = True
14        self._update(1, 0, self.n - 1, i)
15
16    def _update(self, node, left, right, index):
17        if left == right:
18            self.tree[node] = True
19            return
20
21        mid = (left + right) // 2
22        if index <= mid:
23            self._update(node * 2, left, mid, index)
24        else:
25            self._update(node * 2 + 1, mid + 1, right, index)
26
27        new_value = self.tree[node * 2] and self.tree[node * 2 + 1]
28        if self.tree[node] == new_value:
29            return
30        self.tree[node] = new_value

val(i) is obviously O(1) because it is just an array lookup.

Why change(i) Can Be Amortized O(1)

In the worst individual case, updating a leaf can touch O(log n) nodes on the path to the root. But because values only move from false to true, each tree node flips from false to true at most once during the entire lifetime of the data structure.

That means total propagation work across many updates is bounded by the number of tree nodes, which gives amortized constant update cost over a long sequence of change operations.

This amortized argument would break immediately if values could change back to false.

Implement find(i) with Left and Right Searches

To find the closest false to index i, search left and right for the nearest interval that still contains a false, then take the closer result.

1    def find(self, i):
2        if not self.values[i]:
3            return i
4
5        left = self._find_rightmost_false(1, 0, self.n - 1, 0, i - 1)
6        right = self._find_leftmost_false(1, 0, self.n - 1, i + 1, self.n - 1)
7
8        if left is None:
9            return right
10        if right is None:
11            return left
12        return left if i - left <= right - i else right
13
14    def _find_leftmost_false(self, node, left, right, ql, qr):
15        if qr < left or right < ql or self.tree[node]:
16            return None
17        if left == right:
18            return left
19
20        mid = (left + right) // 2
21        result = self._find_leftmost_false(node * 2, left, mid, ql, qr)
22        if result is not None:
23            return result
24        return self._find_leftmost_false(node * 2 + 1, mid + 1, right, ql, qr)
25
26    def _find_rightmost_false(self, node, left, right, ql, qr):
27        if qr < left or right < ql or self.tree[node]:
28            return None
29        if left == right:
30            return left
31
32        mid = (left + right) // 2
33        result = self._find_rightmost_false(node * 2 + 1, mid + 1, right, ql, qr)
34        if result is not None:
35            return result
36        return self._find_rightmost_false(node * 2, left, mid, ql, qr)

Each search descends the tree in O(log n) time because fully true intervals are skipped immediately.

Common Pitfalls

• Ignoring the one-way false -> true constraint. That monotonicity is what makes the amortized bound plausible.
• Trying to solve everything with only an array. find(i) becomes too slow.
• Using only a balanced tree of true or false indices and forgetting that val(i) is required to be constant-time.
• Assuming worst-case change(i) is O(1). The guarantee here is amortized, not per-operation worst case.

Summary

• Use a raw boolean array for val(i) and a segment tree for interval summaries.
• Store whether each interval is entirely true.
• 'val(i) is O(1) from the array.'
• 'find(i) is O(log n) by descending only into intervals that still contain a false.'
• 'change(i) is amortized O(1) because each tree node can switch from false to true only once.'