As pointed out in another post, the way timezone rule changes are stored actually does effectively what you are saying. For each time zone / locale, when there is a rule change, it is appended to the existing rules along with the date of the change. Example from the tzdata2015b file for the New_York time zone:

    # Zone	NAME		GMTOFF	RULES	FORMAT	[UNTIL]
    Zone America/New_York	-4:56:02 -	LMT	1883 Nov 18 12:03:58
			-5:00	US	E%sT	1920
			-5:00	NYC	E%sT	1942
			-5:00	US	E%sT	1946
			-5:00	NYC	E%sT	1967
			-5:00	US	E%sT