Lots and lots of insulation from the ground---pine or juniper boughs, leaves, etc., and covered with a couple of hair-on raw deer hides. And a buffalo hide over that. Then a couple of blankets, another buffalo hide if you've got one, and an oilcloth over all.
I don't know about digging a trench for a fire, I was digging post holes today, and the ground is already frozen down several inches. A couple more weeks, and I'd have better luck digging in concrete.
When the temps get low-- minus 30 degrees or so--keep a fire going all night. Wake up every couple of hours, and punch up the fire, get warm and get some more sleep. This works best with others, so you can take it in turns.
Rod