sqlite index to optimize NOT queries

When I make an index in sqlite, it optimizes queries for that key. But sometimes I want to find records that exclude certain values of that key, and my index doesn't seem to be used to optimize those, at all. I can't figure out how to write an index to optimize a query that matches NOT on a key.

This is an example of what I'm talking about:

CREATE TABLE place (
  id INTEGER PRIMARY KEY,
  thing INTEGER NOT NULL, 
  thekey INTEGER NOT NULL,
  unique(thing,thekey));

CREATE INDEX bythekeys ON place(thekey);

EXPLAIN QUERY PLAN SELECT thing FROM place WHERE NOT thekey = ?;
-- => 0     0              0     SCAN TABLE place
EXPLAIN QUERY PLAN SELECT thing FROM place WHERE thekey = ?;
-- => 0     0              0     SEARCH TABLE place USING INDEX bythekeys (thekey=?)

CREATE INDEX bythenotkeys ON ........?

The "bythekeys" index optimizes queries that look up records by that key, unless the query uses the logical negation of that lookup. Whether using NOT, or != it doesn't seem to make a difference. It always just scans the whole table without using any index. Do I make, like... a partial index or something? How do I optimize NOT queries?