Lazy Array: Implement Range Update and Point Query with Deferred Propagation

Question

## Problem

Implement a `LazyArray` that supports bulk range updates efficiently. All values start at 0.

- `update(l, r, val)` — add `val` to every element in index range `[l, r]` inclusive.
- `query(i)` — return the current value at index `i`.
- `range_query(l, r)` — return the sum of elements in `[l, r]`.

Naive O(n) updates are not acceptable. Use lazy propagation.

```python
class LazyArray:
    def __init__(self, n: int): ...
    def update(self, l: int, r: int, val: int) -> None: ...
    def query(self, i: int) -> int: ...
    def range_query(self, l: int, r: int) -> int: ...
```

```
n = 5, all zeros: [0, 0, 0, 0, 0]
update(1, 3, 4) -> [0, 4, 4, 4, 0]
update(2, 4, 2) -> [0, 4, 6, 6, 2]
query(2)        -> 6
range_query(1,4)-> 18
```

## Follow-ups

1. What is the time complexity of your `update` and `range_query` with a segment tree + lazy propagation?
2. If updates are multiplicative instead of additive, how does the lazy tag change?
3. Can you implement this with a Fenwick tree (BIT) instead? What operation would you need two BITs for?
4. How does your implementation behave with negative `val` updates? Walk through an example.

Lazy Array: Implement Range Update and Point Query with Deferred Propagation

Question Details

Full Details

Topics

More from Databricks