I know that Kyra uses dirty rectangles to update the display efficiently. I haven't looked at such logic before, but someone on the indiegamer forums posted some dirty rectangle code that his company uses. It's free and as-is, so if you find anything useful, you could probably add it to Kyra without any legal/copyright issues. Apparently it does some interesting stuff, but again I haven't looked at Kyra's code to really know.
I appreciate the pointer, but the DR code is Kyra is pretty well optimized. It's key performance problem is actually around the 64-bit fixed numbers, more so than the DR code.