Đặt ~f_i =0~ nếu ~a_{i−1}~ là ước của ~a_i~ và ~f_i = i~ nếu ~a_{i−1}~ không phải là ước của ~a_i~. Suy ra. $$S_i = \max^{i}_{j=1}f_i$$

Xây dựng segment tree mà mỗi node trong cây lưu giá trị max ~f_i~ trong đoạn node đó quản lý. Như vậy ta có thể dễ dàng tính được ~S_i~ thông qua segment tree.

Khi thay đổi giá trị của ~a_i~, chỉ có ~f_i~ và ~f_{i+1}~ là có thể thay đổi do đó ta chỉ cần cập nhật lại 2 vị trí này trong segment tree.

Độ phức tạp: ~O(n · log_2n)~