A map data distribution server that is connected to a network and configured to distribute map data via the network, the map data distribution server comprising an interface connected to the network, a processor connected to the interface, and a storage device connected to the processor, wherein the map data distribution server holds first map data and second map data that is of a newer version than the first map data and holds a plurality of update data including an instruction to update the first map data for each of partitions of a given size on a map, and wherein the map data distribution server is configured to decide whether a predetermined condition is fulfilled upon receiving an update request to update the first map data in a first partition out of the partitions to the second map data from a terminal communicating with the map data distribution server via the network, to select one of the plurality of update data relevant to the first partition, based on the result of the decision, and to transmit the selected update data to the terminal, characterized in that the map data distribution server holds update right information mapping between one or more terminals and a region for which each terminal has an update right to update the first map data stored on the terminal to the second map data, wherein the plurality of update data for each said partition comprises first update data including an instruction to update the first map data in each said partition to the second map data and second update data including an instruction to add a graphic object showing a region for which an update right is not granted to update the first map data to the second map data, wherein, as the decision as to whether a predetermined condition is fulfilled, the map data distribution server is configured to decide whether the first partition includes a region for which the terminal that transmitted the update request has the update right to update the first map data to the second map data, based on information identifying the terminal that transmitted the update request included in the received update request and the update right information, wherein the map data distribution server is configured to select the first update data, if it has been decided that the first partition includes a region for which the terminal that transmitted the update request has the update right to update the first map data to the second map data, and wherein the map data distribution server is configured to select the second update data, if it has been decided that the first partition does not include a region for which the terminal that transmitted the update request has the update right to update the first map data to the second map data, and wherein the first update data comprises road update data including information instructing to update a road network and background update data including information instructing to add, delete, or alter a graphic object showing a planimetric feature other than roads on the map, and wherein the second update data does not include the road update data, but comprises, as the background update data, an instruction to add a graphic object showing a region for which an update right is not granted to update the first map data to the second map data.