No, that’s not necessary. The only thing they need to do is to find an I-Frame (which there are plenty of), make a cut at that frame, show the ad instead, and then resume to the original video after the ad is done. No extra encoding is involved. It’s just like concatenating video files together.

I’ve done similar stuff like this. It’s not too difficult, at least not in H264. Not sure about YouTube’s own format, but I guess it’s quite similar.