What is the time complexity of difference array?

Best case O(1) per update. Worst case O(n + q). Space complexity is O(n).

Difference array

medium

The exact inverse of a prefix sum. Two writes apply an increment to any range, however wide, and a single pass turns the differences back into values.

Best O(1) per updateWorst O(n + q)Space O(n)

Loading the difference array engine…

Where to go next

Prefix sums

easy

Precompute once, answer every range query in O(1).

Fenwick tree (BIT)

hard

Prefix sums in one array, driven by the lowest set bit.

Segment tree

hard

Range queries and point updates, both O(log n).