Postgres: Efficient schema for querying with one exact string match and two range matches

The table I need to query:

CREATE TABLE regions (     state text NOT NULL,     zip_begin text NOT NULL,  -- 9-digit zip code     zip_end text NOT NULL,     date_begin date NOT NULL,     date_end date,      data ..., ) 

There are ~50 states and between 0-5M rows per state. The zip and date ranges might overlap.

The following will be one of the most common queries in my OLTP application:

SELECT data FROM regions WHERE state = {state}   AND {date} BETWEEN date_begin AND date_end   AND {zip} BETWEEN zip_begin AND zip_end 

This query usually yields one row, but may sometimes yield more.

From the Postgres docs, it sounds like a GiST index might do what I need, but I don’t really understand how those work.