Wiki › Thuật toán › Hồi quy đơn điệu (Isotonic Regression, PAVA)

Hồi quy đơn điệu (Isotonic Regression, PAVA)

Tìm dãy không giảm gần một dãy cho trước nhất theo tổng sai số bình phương (có trọng số) bằng thuật toán gộp khối PAVA trong O(n). Kèm biến thể chuẩn L1 (trị tuyệt đối) giải bằng slope trick.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 13 phút 3 lượt xem

Hồi quy đơn điệu (isotonic regression) là bài toán: cho dãy y1,…,yn và trọng số dương w1,…,wn, tìm dãy không giảm b1≤b2≤⋯≤bn (số thực) làm nhỏ nhất tổng sai số bình phương

∑i=1nwi(yi−bi)2.

Thuật toán gộp các khối liền kề vi phạm (Pool Adjacent Violators Algorithm, viết tắt PAVA) giải bài này trong O(n) bằng một ngăn xếp, đủ cho n tới 106. Trong lập trình thi đấu, bài toán thường xuất hiện dưới dạng "chỉnh dãy thành dãy không giảm (hoặc không tăng) với chi phí bình phương nhỏ nhất", hoặc được che giấu sau một phép đổi biến (ví dụ (Ai−RiBi)2=Bi2(Ai/Bi−Ri)2 là hồi quy đơn điệu với yi=Ai/Bi, wi=Bi2).

Biến thể với chi phí trị tuyệt đối ∑|yi−bi| (chuẩn L1) cũng là hồi quy đơn điệu, nhưng giá trị của mỗi khối là trung vị thay vì trung bình. Bài viết trình bày cả hai.

Ý tưởng / Trực giác

Lời giải là các khối hằng. Lời giải tối ưu chia dãy thành các khối liên tiếp, trong mỗi khối mọi bi bằng nhau. Nếu một khối B có chung giá trị v thì

∑i∈Bwi(yi−v)2=WB(v−y¯B)2+hằng số,WB=∑i∈Bwi,  y¯B=∑i∈BwiyiWB,

nên giá trị tốt nhất của khối là trung bình có trọng số y¯B. Quan trọng hơn: với mọi phần còn lại của bài toán, một khối hành xử y như một phần tử duy nhất có giá trị y¯B và trọng số WB.

Bổ đề gộp. Nếu hai phần tử (hay hai khối) liền kề vi phạm, tức yi>yi+1, thì mọi lời giải tối ưu có bi=bi+1.

Chứng minh. Giả sử bi<bi+1. Nếu bi≥yi thì bi+1>bi≥yi>yi+1. Vậy luôn có bi<yi hoặc bi+1>yi+1. Trường hợp đầu, tăng bi thêm một lượng rất nhỏ: dãy vẫn không giảm (vì bi<bi+1) và sai số tại i giảm. Trường hợp sau, giảm bi+1 tương tự. Cả hai đều mâu thuẫn với tính tối ưu.

Thuật toán. Bổ đề cho phép gộp hai phần tử vi phạm thành một phần tử mới (trung bình, tổng trọng số), rồi lặp lại cho tới khi dãy các khối có trung bình tăng dần. Khi đó đặt bi=y¯B là lời giải, vì nó không giảm và mỗi khối đã đạt cực tiểu riêng. Cài đặt bằng ngăn xếp: duyệt từ trái sang phải, đẩy phần tử mới thành một khối; chừng nào khối ở đỉnh có trung bình ≥ khối mới thì gộp. Một lần gộp có thể làm trung bình khối mới giảm xuống và lại vi phạm với khối bên dưới, nên phải gộp dây chuyền.

Hàm mục tiêu lồi chặt nên lời giải tối ưu là duy nhất, thứ tự gộp không ảnh hưởng kết quả. Gộp cả khi hai trung bình bằng nhau là vô hại (giá trị chung vẫn vậy) và giữ cho ngăn xếp tăng ngặt.

Chuẩn L1. Với ∑wi|yi−v|, giá trị tốt nhất của một khối là trung vị có trọng số, và bổ đề gộp vẫn đúng với cùng chứng minh. Có thể cài PAVA với cấu trúc gộp được để lấy trung vị, nhưng cách ngắn nhất là slope trick với một max-heap: duyệt từng ai, đẩy vào heap; nếu phần tử lớn nhất trong heap lớn hơn ai thì cộng chênh lệch vào đáp án, lấy nó ra và đẩy ai thêm lần nữa.

Ví dụ chạy tay

Dãy y=(1,4,2,3,6,0,5), mọi trọng số bằng 1. Mỗi khối ghi dưới dạng (trung bình, số phần tử):

Bước yi Gộp với Ngăn xếp sau bước (đáy bên trái)
1 1 (1,1)
2 4 (1,1) (4,1)
3 2 (4,1) vì 4≥2 (1,1) (3,2)
4 3 (3,2) vì 3≥3 (1,1) (3,3)
5 6 (1,1) (3,3) (6,1)
6 0 (6,1) rồi (3,3): dây chuyền (1,1) (3,5)
7 5 (1,1) (3,5) (5,1)

Ở bước 6, khối mới {0} gộp với {6} thành trung bình 3, vẫn ≤ khối (3,3) bên dưới nên gộp tiếp thành {4,2,3,6,0} có trung bình 15/5=3.

khối:  [1] [ 4   2   3   6   0 ] [5]
y   :   1    4   2   3   6   0    5
b   :   1    3   3   3   3   3    5

Chi phí: 0+1+1+0+9+9+0=20. Với chuẩn L1 (cùng dãy), slope trick cho đáp án 8, đạt tại ví dụ b=(1,2,2,3,3,3,5): 0+2+0+0+3+3+0=8.

Cài đặt

PAVA cho chuẩn L2 có trọng số

Dữ liệu: n, dãy số nguyên y1..yn, dãy trọng số nguyên dương w1..wn. In chi phí nhỏ nhất và dãy b. Mọi tổng được giữ bằng số nguyên, phép so sánh trung bình dùng nhân chéo, và chi phí mỗi khối QW−S2W có tử số tính chính xác bằng __int128 (giả sử ∑wiyi2 vừa long long).

C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;

// Một khối liên tiếp: W = tổng trọng số, S = tổng w*y, Q = tổng w*y^2, cnt = số phần tử
struct Block {
    ll W, S, Q;
    int cnt;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> y(n), w(n);
    for (auto& v : y) cin >> v;
    for (auto& v : w) cin >> v;

    vector<Block> st;  // ngăn xếp khối, trung bình S/W tăng ngặt từ đáy lên đỉnh
    for (int i = 0; i < n; i++) {
        Block cur{w[i], w[i] * y[i], w[i] * y[i] * y[i], 1};
        // đỉnh có trung bình >= khối mới: vi phạm (hoặc bằng), gộp lại
        // so sánh S_top / W_top >= S_cur / W_cur bằng nhân chéo (W > 0)
        while (!st.empty() && (i128)st.back().S * cur.W >= (i128)cur.S * st.back().W) {
            Block& t = st.back();
            cur = {cur.W + t.W, cur.S + t.S, cur.Q + t.Q, cur.cnt + t.cnt};
            st.pop_back();
        }
        st.push_back(cur);
    }

    // chi phí một khối = Q - S^2/W = (Q*W - S^2) / W, tử số tính chính xác bằng __int128
    long double cost = 0;
    for (auto& b : st) cost += (long double)((i128)b.Q * b.W - (i128)b.S * b.S) / b.W;
    cout << fixed << setprecision(6) << (double)cost << '\n';
    // dãy b: mỗi phần tử trong khối nhận trung bình của khối
    for (auto& b : st)
        for (int k = 0; k < b.cnt; k++) cout << (double)((long double)b.S / b.W) << ' ';
    cout << '\n';
}
Python
import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    y = [int(x) for x in data[1 : 1 + n]]
    w = [int(x) for x in data[1 + n : 1 + 2 * n]]

    # Ngăn xếp khối, mỗi khối [W, S, Q, cnt]: tổng w, tổng w*y, tổng w*y^2, số phần tử
    st = []
    for i in range(n):
        cW, cS, cQ, cc = w[i], w[i] * y[i], w[i] * y[i] * y[i], 1
        # đỉnh có trung bình >= khối mới: gộp (so sánh nhân chéo, số nguyên chính xác)
        while st and st[-1][1] * cW >= cS * st[-1][0]:
            tW, tS, tQ, tc = st.pop()
            cW, cS, cQ, cc = cW + tW, cS + tS, cQ + tQ, cc + tc
        st.append((cW, cS, cQ, cc))

    # chi phí khối = (Q*W - S^2) / W, tử số là số nguyên chính xác
    cost = sum((Q * W - S * S) / W for W, S, Q, _ in st)
    b = []
    for W, S, Q, c in st:
        b += ["%.6f" % (S / W)] * c
    sys.stdout.write("%.6f\n%s\n" % (cost, " ".join(b)))


main()
Chuẩn L1: số thao tác ±1 ít nhất để dãy không giảm

Dữ liệu: n rồi dãy số nguyên a1..an. In chi phí nhỏ nhất và một dãy b tối ưu. Đỉnh heap sau bước i là giá trị cuối tối ưu khi chỉ xét i phần tử đầu; dãy các đỉnh này không đơn điệu, nên khôi phục bằng cách đi ngược và lấy min.

C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n), top(n);
    priority_queue<long long> pq;  // các điểm gãy bên trái điểm cực tiểu (max-heap)
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pq.push(a[i]);
        if (pq.top() > a[i]) {      // phần tử lớn nhất đứng trước lớn hơn a[i]: vi phạm
            ans += pq.top() - a[i]; // trả chi phí kéo hai giá trị về cùng một mức
            pq.pop();
            pq.push(a[i]);
        }
        top[i] = pq.top();          // giá trị cuối tối ưu khi chỉ xét i+1 phần tử đầu
    }
    // khôi phục: đi ngược, b[i] = min(top[i], b[i+1])
    vector<long long> b(n);
    b[n - 1] = top[n - 1];
    for (int i = n - 2; i >= 0; i--) b[i] = min(top[i], b[i + 1]);
    cout << ans << '\n';
    for (int i = 0; i < n; i++) cout << b[i] << (i + 1 < n ? ' ' : '\n');
}
Python
import heapq
import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1 : 1 + n]]
    pq = []  # max-heap bằng cách lưu số đối
    top = [0] * n
    ans = 0
    for i in range(n):
        heapq.heappush(pq, -a[i])
        if -pq[0] > a[i]:  # phần tử lớn nhất đứng trước lớn hơn a[i]: vi phạm
            ans += -pq[0] - a[i]  # trả chi phí kéo hai giá trị về cùng một mức
            heapq.heapreplace(pq, -a[i])
        top[i] = -pq[0]  # giá trị cuối tối ưu khi chỉ xét i+1 phần tử đầu
    # khôi phục: đi ngược, b[i] = min(top[i], b[i+1])
    b = [0] * n
    b[n - 1] = top[n - 1]
    for i in range(n - 2, -1, -1):
        b[i] = min(top[i], b[i + 1])
    print(ans)
    print(" ".join(map(str, b)))


main()

Muốn dãy tăng ngặt b1<b2<⋯ (với bi nguyên) thì đặt ai′=ai−i rồi giải bài không giảm: bi<bi+1⟺bi−i≤bi+1−(i+1). Muốn dãy không tăng thì đảo ngược dãy (hoặc đổi dấu).

Độ phức tạp

Phiên bản Thời gian Bộ nhớ
PAVA, chuẩn L2 (có trọng số) O(n) O(n)
Slope trick, chuẩn L1 O(nlogn) O(n)

Vì sao PAVA là O(n)? Mỗi phần tử được đẩy vào ngăn xếp đúng một lần như một khối mới, và mỗi lần gộp làm số khối giảm đi một. Tổng số lần gộp không quá n−1, dù một bước có thể gộp dây chuyền nhiều lần. Trên máy thử, n=106 chạy khoảng 0,06 giây với C++ và 0,4 giây với Python.

Chuẩn L1: mỗi phần tử gây tối đa hai thao tác heap O(logn).

⚠️ Lỗi thường gặp

  • Không gộp dây chuyền: chỉ gộp khối mới với đỉnh một lần là sai. Ở bước 6 của ví dụ, khối {6,0} có trung bình 3 vẫn vi phạm (hoặc bằng) với khối bên dưới; phải dùng while, không phải if.
  • Lấy max tiền tố thay vì trung bình: đặt bi=max(y1,…,yi) cho dãy không giảm nhưng không tối ưu (ví dụ y=(2,0): max tiền tố cho chi phí 4, còn tối ưu là b=(1,1) với chi phí 2).
  • Mất chính xác khi tính chi phí: công thức ∑yi2−∑BSB2/WB bằng số thực trừ hai số rất lớn gần bằng nhau, đáp án nhỏ sẽ mất hết chữ số có nghĩa. Tính tử số QBWB−SB2 chính xác bằng số nguyên (__int128 nếu cần) cho từng khối rồi mới chia. Với dữ liệu thập phân (ví dụ 3 chữ số sau dấu phẩy) thì nhân lên thành số nguyên trước.
  • So sánh trung bình bằng phép chia: S1 / W1 >= S2 / W2 với số thực có thể sai khi hai trung bình bằng nhau hoặc rất gần nhau. Dùng nhân chéo S1 * W2 >= S2 * W1 (trọng số dương nên không đổi chiều).
  • Sai chiều đơn điệu: đề yêu cầu dãy không tăng (R1≥R2≥⋯) thì điều kiện gộp đảo thành "đỉnh có trung bình ≤ khối mới", hoặc đảo ngược dãy rồi giải bài không giảm.
  • Dùng trung bình cho chuẩn L1: với ∑|yi−bi| giá trị của khối là trung vị, không phải trung bình. Dùng nhầm PAVA trung bình sẽ cho đáp án sai (và thường không nguyên).

Biến thể / Mở rộng

  • Chuẩn L1 và tăng ngặt: xử lý bằng slope trick như phần cài đặt; phép đổi biến ai−i chuyển tăng ngặt về không giảm.
  • Mọi bi phải nằm trong cùng một đoạn [L,U]: chạy PAVA rồi cắt giá trị mỗi khối vào [L,U]; kết quả vẫn tối ưu.
  • Ràng buộc trên cây (cha ≤ con) hay trên thứ tự bộ phận tổng quát: không còn ngăn xếp đơn giản; trên cây có thể gộp các khối bằng heap gộp được hoặc DSU theo kiểu nhỏ vào lớn.
  • Liên hệ: ngăn xếp các khối có trung bình tăng dần là một dạng ngăn xếp đơn điệu; tư tưởng "gộp hai phần tử phải bằng nhau" là một lập luận tham lam đổi chỗ.

Bài tập luyện

  • Dãy số (dhbb26dx0710_b): (Hard) Chi phí ∑|ai−bi| nhỏ nhất để dãy thành không giảm: hồi quy đơn điệu chuẩn L1, quy hoạch động trên giá trị hoặc slope trick.
  • Dãy không giảm (dhbb25dx0511_seq): (Very Hard) Cùng mô hình chuẩn L1 với dãy dài hơn; nghiệm tối ưu chỉ dùng giá trị có trong dãy, giải bằng slope trick với max-heap.
  • Dãy số không giảm (thhv19cpt10_b): (Very Hard) Số thao tác ±1 ít nhất để dãy thành không giảm, chính là hồi quy đơn điệu chuẩn L1, giải bằng slope trick với max-heap.
  • Đồng hiđroxit (icpc21mtc): (Very Hard) Tìm dãy không giảm gần nhất theo khoảng cách Euclid với n tới 106: PAVA chuẩn L2 không trọng số, nhân dữ liệu lên 1000 và tính chi phí khối bằng số nguyên 128 bit.
  • Làm dãy tăng nghiêm ngặt (ck04inc): (Very Hard) Dãy tăng ngặt gần nhất theo chuẩn L1: đổi biến ci=ai−i để bỏ chữ "ngặt", rồi hồi quy đơn điệu chuẩn L1 bằng slope trick.
  • Tổng bình phương (icpc22mne): (Very Hard) Cực tiểu ∑(Ai−RiBi)2 với R không tăng: đổi biến thành hồi quy đơn điệu có trọng số wi=Bi2, mỗi khối lưu ba tổng ∑A2,∑AB,∑B2.
  • Dãy xấp xỉ tăng (voi18_seq): (Very Hard) Dãy nguyên tăng ngặt gần nhất theo chuẩn L1, kèm in dãy: đổi biến ai−i rồi hồi quy đơn điệu chuẩn L1, khôi phục dãy bằng đỉnh heap sau từng bước như phần cài đặt.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0