Sử dụng cây nhị phân lập chỉ mục cho một phần mở rộng RMQ

Question

Các RMQ problem thể được mở rộng như vậy:

Do là một mảng số nguyên nA.

truy vấn (x, y): cho hai số nguyên 1 ≤ x, y ≤ n, tìm ra tối thiểu là A[x], A[x+1], ... A[y];

cập nhật (x, v): đưa ra một số nguyên v và 1 ≤ x ≤ n làm A[x] = v.

Sự cố này có thể được giải quyết trong O(log n) cho cả hai hoạt động sử dụng segment trees.

Đây là giải pháp hiệu quả trên giấy, nhưng trên thực tế, phân khúc cây liên quan đến rất nhiều chi phí, đặc biệt nếu được triển khai đệ quy.

Tôi biết thực tế rằng có một cách để giải quyết vấn đề trong O(log^2 n) cho một (hoặc cả hai, tôi không chắc) về hoạt động, sử dụng cây được lập chỉ mục nhị phân (có thể tìm thấy nhiều tài nguyên hơn, nhưng this và this là IMO, ngắn gọn và đầy đủ nhất, tương ứng). Giải pháp này, cho các giá trị của n phù hợp với bộ nhớ, nhanh hơn trong thực tế, vì BIT có chi phí thấp hơn rất nhiều.

Tuy nhiên, tôi không biết cấu trúc BIT được sử dụng như thế nào để thực hiện các thao tác đã cho. Tôi chỉ biết cách sử dụng nó để truy vấn một khoảng thời gian ví dụ. Làm thế nào tôi có thể sử dụng nó để tìm tối thiểu?

Nếu nó giúp, tôi có mã mà người khác đã viết để làm những gì tôi yêu cầu, nhưng tôi không thể hiểu được. Dưới đây là một mảnh như mã:

int que(int l, int r) { 
    int p, q, m = 0; 

    for(p=r-(r&-r); l<=r; r=p, p-=p&-p) { 
     q = (p+1 >= l) ? T[r] : (p=r-1) + 1; 
     if(a[m] < a[q]) 
      m = q; 
    } 

    return m; 
} 

void upd(int x) { 
    int y, z; 
    for(y = x; x <= N; x += x & -x) 
     if(T[x] == y) { 
      z = que(x-(x&-x) + 1, x-1); 
      T[x] = (a[z] > a[x]) ? z : x; 
     } 
     else 
      if(a[ T[x] ] < a[ y ]) 
       T[x] = y; 
} 

Trong đoạn mã trên, T được khởi tạo bằng 0, a là mảng nhất định, N kích thước của nó (họ làm chỉ mục từ 1 vì lý do gì) và upd được gọi tại đầu tiên cho mọi giá trị đọc. Trước khi upd được gọi là a[x] = v được thực hiện.

Ngoài ra, p & -p cũng giống như p^(p & (p - 1)) trong một số nguồn BIT và lập chỉ mục bắt đầu từ 1 với phần tử 0 được khởi tạo thành vô hạn.

Bất cứ ai có thể giải thích cách thức hoạt động ở trên hoặc cách tôi có thể giải quyết vấn đề đã nêu với BIT?

Answer 1

Từ một mức độ cao hơn không quan trọng chút, đây là những gì chúng ta có:

Một BIT mảng bình thường g cho mảng dữ liệu số nguyên a cửa hàng nằm trong khoảng tiền.

g[k] = sum{ i = D(k) + 1 .. k } a[i] 

nơi D(k) chỉ là k với mức thấp nhất bậc 1 bit thiết lập để 0. Ở đây chúng ta có thay

T[k] = min{ i = D(k) + 1 .. k } a[i] 

Các truy vấn hoạt động chính xác như một truy vấn tổng dãy BIT bình thường với sự thay đổi cực tiểu mà của các trang con được thực hiện khi truy vấn được tiến hành thay vì số tiền. Đối với N mục trong a, có các bit (log N) trần trong N, xác định thời gian chạy.

Bản cập nhật mất nhiều công việc hơn vì các yếu tố nhỏ nhất của O (log N) là g - bị ảnh hưởng bởi thay đổi và mỗi lần tự truy vấn O (log N) để giải quyết. Điều này làm cho bản cập nhật O (log^2 n) tổng thể.

Ở cấp độ khó sử dụng, đây là mã thông minh. Câu lệnh x += x & -x xóa chuỗi liên tiếp có thứ tự thấp nhất của 1 trong x và sau đó đặt số không bậc cao nhất tiếp theo là 1. Đây chỉ là những gì bạn cần "duyệt qua" số BIT cho số nguyên gốc x.

Answer 2

Cây phân đoạn cũng là một giải pháp hiệu quả trong thực tế. Tuy nhiên, bạn không thực hiện chúng như cây. Vòng n lên đến sức mạnh tiếp theo của hai và sử dụng một mảng rmq kích thước 2*n. Các mục nhập n cuối cùng của rmq là A. Nếu j < n, sau đó rmq[j] = min(rmq[2*j], rmq[2*j+1]). Bạn chỉ cần xem xét nhiều mục nhập lôgic của rmq để trả lời truy vấn tối thiểu theo phạm vi. Và bạn chỉ cần cập nhật nhiều mục nhập theo lô-gic của rmq khi mục nhập của A được cập nhật.

Tôi không hiểu mã của bạn, vì vậy, tôi sẽ không nhận xét về nó.

Answer 3

Tôi đã không nhìn vào mã cụ thể, nhưng nó có vẻ là khoảng phù hợp với sơ đồ sau:

1) Giữ cấu trúc của BIT, nghĩa là áp đặt một cấu trúc cây dựa trên quyền hạn của hai trên mảng.

2) Tại mỗi nút của cây, giữ giá trị tối thiểu được tìm thấy tại bất kỳ hậu duệ nào của nút đó.

3) Đưa ra một phạm vi tùy ý, đặt con trỏ ở đầu và cuối phạm vi và di chuyển chúng lên trên cho đến khi chúng gặp nhau. Nếu bạn di chuyển một con trỏ lên trên và về phía con trỏ khác thì bạn vừa nhập một nút trong đó mỗi con cháu là một thành viên của dãy, vì vậy hãy lưu ý giá trị đó tại nút đó. Nếu bạn di chuyển con trỏ lên trên và rời khỏi con trỏ khác, nút bạn vừa mới ghép các bản ghi tối thiểu bắt nguồn từ các giá trị bao gồm các giá trị ngoài phạm vi và bạn đã ghi chú mọi giá trị có liên quan bên dưới nút đó trong phạm vi, vì vậy hãy bỏ qua giá trị tại nút đó.

4) Khi hai con trỏ là cùng một con trỏ, mức tối thiểu trong phạm vi là giá trị tối thiểu trong bất kỳ nút nào mà bạn đã lưu ý.