How are games and other applications "patched"?

Both are options, and more as well.

For most games today a new executable is compiled and distributed. How it gets distributed will depend on the game. Sometimes they completely replace the executable with the new executable. Or they may completely replace other files like DLL's, configuration files, or data files. Some systems like Steam will identify which is less work for their system, either a smaller difference applied to a file or a completely new file, and distribute accordingly. This often takes place through a launcher. Few games these days ship with separate launcher apps, instead using systems like Steam, or the Epic Game Store, or Origin, but it used to be fairly common 20 years ago. You'd open up your launcher for Diablo or The Sims or Halo or whatever and a program would check for updates, ask you about game options, then it would launch the game with the right options. One of those steps to check for updates and apply them would download a zip file or similar and unpack it to the correct location.

Sometimes a system will store the differences between versions, download the difference, and apply it on the other side. The developers would provide whatever the difference between the files were, providing the original that shipped with the game and the modified version, which could easily be a recompiled executable or a modified data file. The tools to do it from the early 1970's were called diff and patch which is where the terms tend to come from. The ‘diff’ tool creates a listing of what is different between two files, and the ‘patch’ tool applies those differences. The old diff/patch tools were designed for text files containing source code and configurations, and they are still used for a lot of source code and systems. Tools like git can show differences in that classic format. Back in the heyday of Shareware and dial-up bulletin boards there were several patch systems where the focus was on minimizing size of what was distributed, so the patch files were tightly compressed to efficinetly encode whatever differences need to be applied.

The Wikipedia article linked to the word “diff” above has an example showing how lines are added, removed, or modified.

Another option that isn't done much these days but was needed in the case of cartridges or other ROM-distributed games, was to create a file showing the differences between the two and then manually poke the values into the new rom image. On systems from 40 years ago where the entire memory is measured in bytes or kilobytes and everything was programmed in machine code from the outset, programmers were more likely to know what specific opcodes they needed to modify to change the behavior of the game.

Yet another option that has been done is an overlay system, much like Docker container stacks or other virtual machine systems where you can specify that one file system overlays the other file system. This could be done for example on a system like the Switch where games can be distributed on cartridge or online. The company can transmit a small file to patch the game that includes only the modified files. When the console loads the program it also loads the patch disk. Let's say they're looking for the file /data/file.dat. If the file exists in the patched overlay the OS provides the the /data/file.dat from the patch, if the file doesn't exist on the overlay it provides the original /data/file.dat.

In video game engines and their build systems (Unreal Engine) there is an address sanitizer and address randomization. I believe this would make it hard to “patch” the executable even if you wanted to. There are other tricks in the build system to make it harder on people trying to cheat, or modify the games executable.

Unreal splits up the game contents, assets, settings, static data into “.pak” files - Taking the editor game content and packaging it into a distribution ready set of pak files is called “cooking”. - The game content is where the overwhelming vast majority of data for the game comes from. It's probably 99% to 1% - where 99% is the size of game assets that are not compiled code / dll's, etc.

That being said, Unreal Engine, and Steam have ways to decide how big of “chunks” you want to distribute, and you can even influence what content goes in what chunks… So I might split my game into 100 different “1GB” chunks.
The hope is, if you changed one area of your games content, the changes might be more localized to a given chunk, and that way the whole 100GB game doesn't need to be re-downloaded when you “patch” it.
If you want to read more, here is some literature: https://dev.epicgames.com/documentation/en-us/unreal-engine/cooking-content-and-creating-chunks-in-unreal-engine

Obviously if the patch includes no “content” changes then it's just a matter of updating clients with the executable changes, and that is always fairly trivial.

I know this is Unreal Engine specific, but I hope this was informative.

to keep it simple, think of operations, Push, Pop and Append.