Wenn eine Menge S positiver Ganzzahlen gegeben ist, deren Elemente nicht verschieden sein müssen, muss ich eine minimale nicht negative Summe finden, die aus keiner Teilmenge der gegebenen Menge erhalten werden kann.

Beispiel:if S = {1, 1, 3, 7}, wir können bekommen0 wie(S' = {}), 1 wie(S' = {1}), 2 wie(S' = {1, 1}), 3 wie(S' = {3}), 4 wie(S' = {1, 3}), 5 wie(S' = {1, 1, 3}), aber wir können nicht bekommen6.

Jetzt bekommen wir einsarray A, bestehend ausN positive ganze Zahlen. Ihre sindM Abfragen bestehen jeweils aus zwei ganzen ZahlenLi undRi Beschreiben Sie die folgende Abfrage: Wir müssen diese Summe finden, die nicht aus dem Array abgerufen werden kannelements ={A[Li], A[Li+1], ..., A[Ri-1], A[Ri]} .

Ich weiß, dass es durch einen Brute-Force-Ansatz in O (2 ^ n) zu finden ist. Aber gegeben1 ≤ N, M ≤ 100,000Dies kann nicht getan werden. Also ist ihr jeder wirksame Ansatz, um es zu tun.