Ajax va bene: usa qualche libreria d'appoggio (es. jquery), così dovrai solo richiamare il tuo script con qualcosa come (mettendo la funzione JS nell'evento onclick del link):

Codice PHP:
// QUESTO è JavaScript!!
$.ajax({
  
url"tuoscript.php"// <---- il tuo script (php) di gestione
  
contextdocument.body,
  
success: function(){
    $(
this).addClass("done"); // <---- qui aggiorna in JS l'oggetto
  
}
}); 
...solo per aver un'idea... è più un problema JS, direi... devi richiamare il tuo script php che potrebbe restituire il nuovo valore da usare nello snippet tipo quello di sopra per aggiornare il tag html