Now I'm GUESSING that a patch program would save the differences between program A (old) and program B (new), and then change A accordingly to the changes in B. This would explain for most patches' small size.
If I'm wrong, tell me what's right. If I'm right, tell me how I'd go about making such a program (not an info file, a program that does it itself).